@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;
	}
}