Description
Solution
非常妙的一道题。
首先题目中的判定条件“走到拥有关键点的环”是一个不好判定的条件，那么考虑将问题转化变为好判定的。
将原来的操作“保留一条边其它边全部删除”变为“选择一条边走出去”，同时，将获胜条件从“走到拥有关键点的环”变为“可以无限次经过关键点”。
如果能无限次走到环上，那么就相当于之前的走到有关键点的环上，除非后手选择一条边离开环，火车将一直在环上绕圈不停的走关键点，但是如果后手选择了一条离开环的边，那他在第一次经过那个点的时候就不应该选择走上环的边，但是他走上环是因为在那个点走上环最优，所以会产生矛盾，那么转化后的问题和转化前的问题就是等价的了。
考虑“先手可以无限次走关键点”如何判定，如果先手能走无限次关键点，那么对于所有可能走到的点，先手都能迫使后手走到关键点。
即我们求出图上先手能迫使后手走上关键点的点，如果这些点是全集，则后手在这些点必须无限次的走上关键点。
如果这些点不是关键点，那么这些点的补集，一定是后手获胜，以为后手总可以不走到关键点。
同时，先手能迫使后手走上关键点的点可能不能无限次的走上，当且仅当后手在这些点可以进入之前求过的后手必胜的点集。
那么我们发现先手可能获胜的点集又缩小了，继续在这个缩小后的的点集上搜出先手可能获胜的点集，直到满足该点集就是全集的条件，那么剩下的就是先手必胜的点集。
由于每次迭代总会使先手可能获胜的点集变小，所以最多迭代(O(n))次，每次时间复杂度(O(n + m))，总体最坏是(O(n ^ 2 + nm))，可以通过本题。
Code
#include "train.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 5000;
int vis[N + 50], res;
vector<int> edge1[N + 50], edge2[N + 50];
vector<int> Get(vector<int> a, vector<int> res, vector<int> r, int typ)
{
int n = a.size();
memset(vis, 0, sizeof(vis));
vector<int> ans(N + 50), deg(N + 50);
queue<int> q;
for (int i = 0; i < n; i++) if (r[i] && res[i]) q.push(i), ans[i] = 1;
for (int i = 0; i < n; i++) for (int j = 0; j < edge1[i].size(); j++) if (res[edge1[i][j]]) if (typ ^ a[i]) deg[i]++; else deg[i] = 1;
while (!q.empty())
{
int u = q.front(); q.pop();
for (vector<int>::iterator it = edge2[u].begin(); it != edge2[u].end(); it++)
{
int v = *it;
if (!ans[v] && res[v])
{
deg[v]--;
if (!deg[v]) ans[v] = 1, q.push(v);
}
}
}
return ans;
}
vector<int> who_wins(vector<int>a, vector<int>r, vector<int>u, vector<int>v)
{
int n = a.size(), m = u.size();
vector<int> res(N + 50);
for (int i = 0; i < n; i++) res[i] = 1;
for (int i = 0; i < m; i++) edge1[u[i]].push_back(v[i]), edge2[v[i]].push_back(u[i]);
while (1)
{
int flag = 1;
vector<int> fa = Get(a, res, r, 1);
for (int i = 0; i < n; i++)
if (!fa[i] && res[i])
{
flag = 0;
break;
}
if (flag) return res;
for (int i = 0; i < n; i++) fa[i] ^= 1;
vector<int> fb = Get(a, res, fa, 0);
for (int i = 0; i < n; i++) if (fb[i]) res[i] = 0;
}
return res;
}