[POI2001]Gra绿色游戏

Description

绿色游戏是一种两人游戏，双方分别称Ann和Billy。游戏的内容主要是轮流在棋盘上移动一颗棋子。棋盘上的点一部分是绿色的，其余是白色的；全部从1至a+b编号。编号1至a的点属于Ann，编号(a+1)至(a+b)的点属于Billy。每个点都有一些后继点，均可一步到达。属于Ann的点的后继点一定属于Billy，反之亦然。所有的点都至少有一个后继点，这样总可以往下走一步。游戏开始时把棋子放在任意的一点P上，然后双方轮流移动棋子至当前所在点（属于移动方）的一个后继点上（属于对手）。游戏由点P的拥有者开始，结束时棋子第二次到达了某一点，称点Q。如果在从点Q至点Q的一连串移动中，棋子至少一次被放到绿色点上，则Ann赢。若从点P开始，不管Billy如何移动，Ann总能保证赢得这次游戏，则称Ann对起始点P有必胜的策略。

任务：算出Ann有必胜策略的起始点；

Input

首行有两个整数a和b，两个整数之间用一个空格分开，分别表示属于Ann和Billy的点数(1小于等于a，b小于等于3000)。

以下a+b行是对各点的描述，先描述Ann的点，再描述Billy的点。

第i+1行（1小于等于i小于等于a+b）以整数z，k开始：z表示点i的颜色(O－白色，I－绿色)，k表示后继点的数目。

然后是K个整数（1小于等于k＜a+b），写在同一行，代表点i后继点的编号，这些整数均用一个空格分开。

绿点的个数不超过100，所有点的后继点的个数之和不超过30000。

Output

首行仅一个整数L，代表Ann有L个有必胜策略的起始点。以下L行按升序顺序依次给出这些点的编号。

Sample Input

5 3

0 2 6 7

0 3 6 7 8

0 1 8

1 1 7

1 1 8

1 2 1 2

0 2 1 2

0 2 3 4

Sample Output

5

1

2

4

6

7

维护一个保护集合\(S\)，表示哪些点\(A\)可能胜利。

首先将所有绿点加入\(S\)。

\(1.\)对于一个不在\(S\)的\(A\)点，若它存在某个后继在\(S\)中，则将其加入\(S\)。

\(2.\)对于一个不在\(S\)的\(B\)点，若它所有后继都在\(S\)中，则将其加入\(S\)。

通过拓扑可以\(O(n+m)\)求出\(S\)集合，那么剩下的点\(A\)必败。

\(1.\)对于一个在\(S\)的\(A\)点，若它所有后继都不在\(S\)中，则将其从\(S\)中移除。

\(2.\)对于一个在\(S\)的\(B\)点，若它存在某个后继不在\(S\)中，则将其从\(S\)中移除。

同样可以通过拓扑\(O(n+m)\)求出最终的\(S\)集合。

这样会导致某些绿点不在\(S\)中，那么它们就失去了作为绿点的价值，将其标记为白点。

重复运行这个算法\(O(n)\)轮直到所有绿点都发挥了价值，此时\(S\)中的点\(A\)必胜。

时间复杂度\(O(n(n+m))\)。

/*program from Wolfycz*/

#include<cmath>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

#define inf 0x7f7f7f7f

using namespace std;

typedef long long ll;

typedef unsigned int ui;

typedef unsigned long long ull;

inline int read(){

	int x=0,f=1;char ch=getchar();

	for (;ch<'0'||ch>'9';ch=getchar())	if (ch=='-')    f=-1;

	for (;ch>='0'&&ch<='9';ch=getchar())	x=(x<<1)+(x<<3)+ch-'0';

	return x*f;

}

inline void print(int x){

	if (x>=10)     print(x/10);

	putchar(x%10+'0');

}

const int N=3e3,M=3e4;

int pre[M+10],now[N+10],child[M+10],d[N+10],deg[N+10],h[N+10],Ans[N+10];

bool vis[N+10],c[N+10];

int n,m,tot;

void join(int x,int y){pre[++tot]=now[x],now[x]=tot,d[child[tot]=y]++;}

bool solve(){

	int head=1,tail=0;

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

		vis[i]=c[i],deg[i]=d[i];

		vis[i]?h[++tail]=i:0;

	}

	for (;head<=tail;head++){

		int Now=h[head];

		for (int p=now[Now],son=child[p];p;p=pre[p],son=child[p]){

			if (vis[son])	continue;

			son<=m?vis[h[++tail]=son]=1:!--deg[son]?vis[h[++tail]=son]=1:0;

		}

	}

	head=1,tail=0;

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

		deg[i]=d[i];

		!vis[i]?h[++tail]=i:0;

	}

	for (;head<=tail;head++){

		int Now=h[head];

		for (int p=now[Now],son=child[p];p;p=pre[p],son=child[p]){

			if (!vis[son])	continue;

			son>m?vis[h[++tail]=son]=0:!--deg[son]?vis[h[++tail]=son]=0:0;

		}

	}

	bool flag=0;

	for (int i=1;i<=n;i++)	if (c[i]&&!vis[i])	c[i]=0,flag=1;

	return flag;

}

int main(){

	m=read(),n=read()+m;

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

		c[i]=read(),k=read();

		for (int j=1;j<=k;j++)	join(read(),i);

	}

	while (solve());

	int cnt=0;

	for (int i=1;i<=n;i++)	if (vis[i])	Ans[++cnt]=i;

	printf("%d\n",cnt);

	for (int i=1;i<=cnt;i++)	printf("%d\n",Ans[i]);

	return 0;

}

巴特西

[POI2001]Gra绿色游戏

最新文章

热门文章