P6560 [SBCOI2020] 時光的流逝（DAG圖上博弈模板）
題意：
? 給出一個有向圖（可能有環），每輪游戲有一個起點和終點，A和B一起玩游戲，A先移動，然后他們交替移動，當誰把棋子移動至終點，誰就勝利了，同樣，若是有人無法移動了，就會被判失敗，若A必勝，輸出1，若B必勝，輸出-1，若兩人均無必勝策略，輸出0，
思路：
? 很明顯是一個博弈論，對于這種DAG上的博弈游戲，我們要從終點來考慮問題，分析題目，因為當棋子到達終點或者到達出度為0的點，此時執棋者失敗，所以，終點和出度為0的點是必敗態，這里把出度為0的點也歸到下文終點的定義中，
? 對于圖上的博弈論，有一個很基礎的知識點：若一個點可以到達必敗態，那么這個點是必勝態，若一個點無法達到必敗態，只能到達必勝態，那么這個點是必敗態，
? 因為我們一開始只知道終點的資訊，所以我們應該建一個反圖，然后從終點開始拓撲排序，根據上面的知識點進行模擬，
實作：
? 在拓撲排序的時候要通過出度（反圖的入度）來模擬判斷一個點是否為必勝態，本題還有一個問題就是，什么叫均無必勝策略，那也就是遇到了一個環，比如simple2中的資料，我們在拓撲排序前對他們做標記，若拓撲排序做完之后，終點還沒有進過佇列，那就是環也就是輸出0，
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, n) for (int i = a; i < n; i++)
#define all(x) x.begin(), x.end()
#define pb push_back
#define debug(x) cout << x << endl
#define SZ(x) (int)x.size()
typedef long long ll;
typedef pair<int, int> PII;
const int inf = 0x3f3f3f3f;
string yes = "Yes\n";
string no = "No\n";
const int N = 100005;
int n, m, Q;
int d[N], f[N], back_d[N]; //入度會被更改，所以要備份一下，
vector<int> g[N];
int main()
{
scanf("%d%d%d", &n, &m, &Q);
while (m--)
{
int u, v;
scanf("%d%d", &u, &v);
g[v].pb(u);
d[u]++;
}
while (Q--)
{
int st, ed;
scanf("%d%d", &st, &ed);
queue<int> q;
memcpy(back_d, d, sizeof back_d);
for (int i = 1; i <= n; i++) //入度
{
if (i == ed || !back_d[i])
f[i] = -1, q.push(i); // f --> Lose:-1 Win:1
else
f[i] = 0; //不可達就是0
}
while (q.size())
{
int u = q.front();
q.pop();
for (int v : g[u])
{
if (f[v] != 0)
continue;
back_d[v]--;
if (f[u] == -1) //如果一個點能走到一個必敗點，那就是必勝態
{
f[v] = 1;
q.push(v);
}
else if (!back_d[v])
{
f[v] = -1;
q.push(v);
}
}
}
cout << f[st] << '\n';
}
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/513681.html
標籤：其他