BZOJ1124 [POI2008]枪战Maf

题面在这里

​

考虑最大值，对于每个联通块：

• 单点：死1人
• 环：死\(size-1\)人
• 基环内向树：死\(size-leaf\)人

​

考虑最小值，首先叶子结点不会死

那么叶子结点瞄准的目标一定会死，先打死再说

这时如果导致有新的叶子产生，就又加入队列

最后剩下的每个环，死亡人数为\(\lceil \frac{size}2 \rceil\)

​

示例程序：

#include<cstdio>

const int maxn=1000005;
int n,to[maxn],f[maxn],fa[maxn],s[maxn],sum[maxn],MAX,MIN,que[maxn];
bool vis[maxn];
inline int getfa(int x) {return fa[x]==x?x:fa[x]=getfa(fa[x]);}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&to[i]),fa[i]=i,f[to[i]]++;
	for (int i=1;i<=n;i++) fa[getfa(to[i])]=getfa(i);
	for (int i=1;i<=n;i++) s[getfa(i)]+=(f[i]==0),sum[getfa(i)]++;
	for (int i=1;i<=n;i++)
	 if (getfa(i)==i){
	 	if (sum[i]==1) MAX++;else
	 	if (s[i]==0) MAX+=sum[i]-1;else MAX+=sum[i]-s[i];
	 }
	int hed=0,til=0;
	for (int i=1;i<=n;i++)
	 if (!f[i]) que[++til]=i,vis[i]=1;
	while (hed!=til){
		int x=que[++hed];
		if (!vis[to[x]]) vis[to[x]]=1,MIN++,f[to[to[x]]]--;
		if (!vis[to[to[x]]]&&!f[to[to[x]]]) que[++til]=to[to[x]],vis[to[to[x]]]=1;
	}
	for (int i=1;i<=n;i++) fa[i]=i,s[i]=0;
	for (int i=1;i<=n;i++)
	 if (!vis[i]&&!vis[to[i]]) fa[getfa(to[i])]=getfa(i);
	for (int i=1;i<=n;i++) if (!vis[i]) s[getfa(i)]++;
	for (int i=1;i<=n;i++)
	 if (getfa(i)==i) MIN+=s[i]+1>>1;
	printf("%d %d",MIN,MAX);
	return 0;
}