@2019东北赛F题 Mini-game Before Contest

F. Mini-game Before Contest

题意

两支队伍在一张 n 个点 m 条边的有向图上玩游戏，6 个人
轮流移动棋子行动一步，不能移动的人所属队伍输。
正常人希望赢，不能赢则希望平局；而演员希望输，不能输
则希望平局

思路

我认为这道题只是披着博弈外衣的一道dp题,当时没做出来主要就是因为没想到可以用dp的状态来表示博弈的结果.
f[i][j]表示当前轮到第i个人行动在第j个点的博弈结果,初始化为-1,表示平局,0表示i所在队失败,1表示其所在队胜出
对于出度为0的点可以直接令其f[i][j]值为0
对于其他点我们利用spfa来进行更新
考虑所有的f[u][j+1]，u是i一步可达的点,若有一点值为0则f[i][j]为1,actor则相反(这里大概是用到唯一博弈的地方吧,非常好想)

代码

// 菜鸡对着标程改了好久
#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define ll long long
#define INF 0x3f3f3f3f 
#define MEM(x,y) memset(x,y,sizeof(x))
#define int long long
#define rep(i , a , b) for(int i = a ; i <= b ; i ++)
#define P pair<int,int>
#define sc(a) scanf("%lld",&a)
#define pf(a) printf("%lld ",a)
using namespace std;
const int N = 1000010;
int m, n;
int h[N], e[N],  nx[N], idx;
void add(int a, int b)
{ 
	e[idx] = b, nx[idx] = h[a], h[a] = idx++;
}
string s1, act;
int f[N][6];//dp数组
int du[N][6];//出度
int vis[N][6];//spfa判重
queue<P> q;
signed main() { 
	int T;
	cin >> T;
	while (T--) 
	{ 
		cin >> n >> m;		
		rep(i, 1, n)
		{ 
			h[i] = -1;
			idx = 0;
		}
		rep(i,1,n)
			rep(j,0,5)
				f[i][j] = -1, du[i][j] = 0, vis[i][j] = 0;
		rep(i,0,m-1)
		{ 
			int u, v;
			sc(u);
			sc(v);
			add(v, u);
			for (int j = 0; j < 6; ++j)
				++du[u][j];
		}
		cin >> s1 >> act;
		rep(i,0,5)
			act[i] -= '0';
		rep(i,1,n)
			rep(j,0,5)
				if (du[i][j] == 0) 
				{ 
					vis[i][j] = 1;
					f[i][j] = 0;
					q.push(P(i, j));
				}
		while (!q.empty()) 
		{ 
			P now = q.front(); 
			q.pop();
			int u = now.first;
			int p = now.second;
			for (int i = h[u]; ~i; i = nx[i])
			{ 
				int v = e[i];
				int np = (p + 5) % 6;
				if (vis[v][np]) continue;
				if (s1[p] == s1[np]) 
				{ 
					if (act[np]) 
					{ 
						if (f[u][p] == 1) 
						{ 
							--du[v][np];
							if (du[v][np] == 0) 
							{ 
								f[v][np] = 1;
								vis[v][np] = 1;
								q.push(P(v, np));
							}
						}
						else 
						{ 
							f[v][np] = 0;
							vis[v][np] = 1;
							q.push(P(v, np));
						}
					}
					else 
					{ 
						if (f[u][p] == 1) 
						{ 
							f[v][np] = 1;
							vis[v][np] = 1;
							q.push(P(v, np));
						}
						else
						{  
							--du[v][np];
							if (du[v][np] == 0) 
							{ 
								f[v][np] = 0;
								vis[v][np] = 1;
								q.push(P(v, np));
							}
						}
					}
				}
				else 
				{  
					if (act[np]) 
					{ 
						if (f[u][p] == 1) 
						{ 
							f[v][np] = 0;
							vis[v][np] = 1;
							q.push(P(v, np));
						}
						else 
						{ 
							--du[v][np];
							if (du[v][np] == 0) 
							{ 
								f[v][np] = 1;
								vis[v][np] = 1;
								q.push(P(v, np));
							}
						}
					}
					else 
					{ 
						if (f[u][p] == 1)
						{ 
							--du[v][np];
							if (du[v][np] == 0) 
							{ 
								f[v][np] = 0;
								vis[v][np] = 1;
								q.push(P(v, np));
							}
						}
						else 
						{ 
							f[v][np] = 1;
							vis[v][np] = 1;
							q.push(P(v, np));
						}
					}
				}
			}
		}
		rep(i, 1, n)
			if (f[i][0] == -1)
				cout << "D";
			else if (f[i][0] == 1) 
				cout<<s1[0];
			else 
			{ 
				char c = 'A' + 'B' - s1[0];
				cout << c;
			}
		cout << endl;
	}
}