【BZOJ】1124: [POI2008]枪战Maf

题意

\(n(n < 1000000)\)个人，每个人\(i\)指向一个人\(p_i\)，如果轮到\(i\)了且他没死，则他会将\(p_i\)打死。求一种顺序，问死的人最少和最多的数目。

分析

贪心+乱搞

题解

最多剩下的：

链：(n+1)/2

环：n/2

环套内向树：维护没被杀的点，即用队列维护入度为0的点，然后环变成了一堆链，再用上面的结论即可。

最少剩下的：

链：1

环：1

环套内向树：入度为0的个数

#include <bits/stdc++.h>

using namespace std;

inline int getint() {

	int x=0, c=getchar();

	for(; c<48||c>57; c=getchar());

	for(; c>47&&c<58; x=x*10+c-48, c=getchar());

	return x;

}

const int N=1000005;

int to[N], in[N], q[N];

bool vis[N], del[N];

int main() {

	int n=getint(), ans1=0, ans2=0;

	for(int i=1; i<=n; ++i) {

		++in[to[i]=getint()];

	}

	int *fr=q, *ta=q;

	for(int i=1; i<=n; ++i) {

		if(in[i]==0) {

			++ans1;

			for(int j=i; !vis[j]; vis[j]=1, j=to[j]);

			*ta++=i;

		}

	}

	for(int i=1; i<=n; ++i) {

		if(!vis[i]) {

			int len=0;

			for(int j=i; !vis[j]; vis[j]=1, j=to[j], ++len);

			ans1+=len>1;

		}

	}

	memset(vis, 0, sizeof(bool)*(n+1));

	for(; fr!=ta; ) {

		int x=*fr++, y=to[x];

		vis[x]=1;

		if(!del[x]) {

			++ans2;

			del[y]=1;

		}

		if(!--in[y]) {

			*ta++=y;

		}

	}

	for(int i=1; i<=n; ++i) {

		if(!vis[i] && del[i]) {

			int len=0;

			for(int j=i; !vis[j]; vis[j]=1, j=to[j]) {

				if(!del[j]) {

					++len;

				}

				else {

					ans2+=(len+1)>>1;

					len=0;

				}

			}

			ans2+=(len+1)>>1;

		}

	}

	for(int i=1; i<=n; ++i) {

		if(!vis[i]) {

			int len=0;

			for(int j=i; !vis[j]; vis[j]=1, j=to[j], ++len);

			ans2+=len>>1;

		}

	}

	printf("%d %d\n", n-ans2, n-ans1);

	return 0;

}

巴特西

【BZOJ】1124: [POI2008]枪战Maf

题意

分析

题解

最新文章

热门文章