题目链接：https://uoj.ac/problem/322
分析
“一个点的出边一旦确定就不能改变”这个条件不好处理。通过网上一些题解的分析，可以把问题修改成：
- 结点的主人每次可以指定任意一条出边（即使之前已经指定了另外一条）。
- A 胜利条件：存在一种策略，无论 B 怎么操作，总能使火车无限次经过充电车站。
- B 胜利条件：存在一种策略，无论 A 怎么操作，总能使火车只经过充电车站有限次。
设 \(w_i\) 为：是否存在一种策略，无论 B 怎么操作，从 \(i\) 开始总能到达充电车站。（如果 \(i\) 是充电车站则需要再次到达充电车站，到达自身也行）。
如果一个充电车站 \(i\) 满足 \(w_i=0\)，那么它就没用。考虑每次缩小充电车站的集合，重新计算 \(w\)。这样最多迭代 \(n\) 次，时间复杂度 \(O(nm)\)。
实现
#include<bits/stdc++.h>
#include"train.h"
#define rp(i,a,b) for(int i=a;i<=b;++i)
#define pr(i,a,b) for(int i=a;i>=b;--i)
#define pb push_back
#define sz(x) int(x.size())
using namespace std;
typedef vector<int> vi;
const int N=5e3+9;
int n,m,o[N],d[N];
vi g[N];
queue<int> Q;
vi who_wins(vi a,vi r,vi u,vi v){
n=sz(a),m=sz(u);
rp(i,0,m-1){
g[v[i]].pb(u[i]),++o[u[i]];
}
vi w(n);
auto go=[&](){
rp(i,0,n-1){
w[i]=0;
d[i]=a[i]?1:o[i];
if(r[i]){
Q.push(i);
}
}
for(;!Q.empty();Q.pop()){
int v=Q.front();
for(int u:g[v])if(!--d[u]){
w[u]=1;
if(!r[u]){
Q.push(u);
}
}
}
};
auto chk=[&]()->bool{
rp(i,0,n-1)if(r[i]&&!w[i]){
r[i]=0;
return 0;
}
return 1;
};
while(1){
go();
if(chk()){
return w;
}
}
}