DMOJ IOI '17 P3 - Toy Train【拓扑排序】

传送：https://dmoj.ca/problem/ioi17p3

参考：https://blog.csdn.net/qq_27327327/article/details/80711824

妙啊……首先题意就是走到一个包含充电点的环里就能赢

因为出度至少是1，所以如果所有点都能到充电点那么全部是先手必胜；否则，不能到充点电的点以及一定能到这些点的点就一定是先手必败（能到的不是先手必胜，因为可能到了之后再出去进入别的环）

能到充点电的点是A支配并且能到至少一个充点电的点或B支配只能到充电点的点，每次求出这个集合，判断如果是全集就退出，否则用补集找到先手必败点删去，然后再对剩下不确定的点做上述操作即可

#include<iostream>

#include<cstdio>

#include<vector>

#include<queue>

using namespace std;

const int N=5005;

int n,m;

vector<int>e[N],e2[N];

vector<int>wk(int fl,vector<int>a,vector<int>r,vector<int>b)

{

	vector<int>ans(n),d(n);

	queue<int>q;

	for(int i=0;i<n;i++)

		if(r[i]&&b[i])

			q.push(i),ans[i]=1;

	for(int i=0;i<n;i++)

		for(int j=0;j<e[i].size();j++)

			if(b[e[i][j]])

			{

				if(a[i]^fl)

					d[i]++;

				else

					d[i]=1;

			}

	while(!q.empty())

	{

		int u=q.front();

		q.pop();

		for(int i=0;i<e2[u].size();i++)

			if(!ans[e2[u][i]]&&b[e2[u][i]])

				if(!(--d[e2[u][i]]))

				{

					ans[e2[u][i]]=1;

					q.push(e2[u][i]);

				}

	}

	return ans;

}

vector<int> who_wins(vector<int>a,vector<int>r,vector<int>u,vector<int>v)

{

	n=a.size(),m=u.size();

	for(int i=0;i<m;i++)

		e[u[i]].push_back(v[i]),e2[v[i]].push_back(u[i]);

	vector<int>ans(n);

	for(int i=0;i<n;i++)

		ans[i]=1;

	while(1)

	{

		int fl=1;

		vector<int>b1=wk(1,a,r,ans);

		for(int i=0;i<n;i++)

			if(ans[i]&&!b1[i])

				fl=0;

		if(fl)

			return ans;

		for(int i=0;i<n;i++)

			b1[i]^=1;

		vector<int>b2=wk(0,a,b1,ans);

		for(int i=0;i<n;i++)

			if(b2[i])

				ans[i]=0;

	}

	return ans;

}

巴特西

DMOJ IOI '17 P3 - Toy Train【拓扑排序】

最新文章

热门文章