題目:http://acm.hdu.edu.cn/showproblem.php?pid=1524

題意:在一個(gè)有向無環(huán)圖上有n個(gè)頂點(diǎn),每一個(gè)頂點(diǎn)都只有一個(gè)棋子,有兩個(gè)人,每次根據(jù)這個(gè)圖只能將任意一顆棋子移動(dòng)一步

,如果到某一步玩家不能移動(dòng)時(shí),那么這個(gè)人就輸.

分析:本題是最典型的有向無環(huán)圖的博弈,利用dfs把所有頂點(diǎn)的SG值都計(jì)算出來,然后對(duì)每個(gè)棋子的SG值進(jìn)行異或運(yùn)算,如果

為0就是先手必?cái)?否則就是先手必勝.

如果某個(gè)人移動(dòng)到出度為0的頂點(diǎn),那么他必?cái)?在這里首先介紹一下什么是SG函數(shù).

對(duì)于給定的有向無環(huán)圖,定義圖中每個(gè)頂點(diǎn)的Sprague-Grundy函數(shù)g如下：g(x) = mex{ g(y) | y是x的后繼 }。

mex(x)表示最小的不屬于這個(gè)集合的非負(fù)整數(shù)。例如：mex{0,1,2,4} = 3、mex{2,3,5} = 0、mex{ } = 0。

SG函數(shù)的性質(zhì):首先,所有終結(jié)點(diǎn)所對(duì)應(yīng)的頂點(diǎn)，也就是出度為0的頂點(diǎn)，其SG值為0，因?yàn)樗暮罄^集合是空集。然后對(duì)于一

個(gè)g(x) = 0的頂點(diǎn)x，它的所有后繼y都滿足g(y)!=0。對(duì)于一個(gè)g(x)!=0的頂點(diǎn)，必定存在一個(gè)后繼y滿足g(y)=0.

而求整個(gè)SG函數(shù)值的過程就是一個(gè)對(duì)有向無環(huán)圖進(jìn)行深搜過程.

#include <iostream> #include <string.h> #include <stdio.h>using namespace std; const int N = 2005;int head[N]; int n,m,cnt;struct Edge {int to;int next; };Edge edge[N*N]; int SG[N];void Init() {cnt = 0;memset(SG,-1,sizeof(SG));memset(head,-1,sizeof(head)); }void add(int u,int v) {edge[cnt].to = v;edge[cnt].next = head[u];head[u] = cnt++; }int mex(int x) {if(SG[x] != -1) return SG[x];bool vis[N];memset(vis,0,sizeof(vis));for(int i=head[x];~i;i=edge[i].next){int v = edge[i].to;SG[v] = mex(v);vis[SG[v]] = 1;}for(int i=0;;i++)if(!vis[i]) return i; }int main() {while(~scanf("%d",&n)){Init();for(int i=0;i<n;i++){scanf("%d",&m);while(m--){int u;scanf("%d",&u);add(i,u);}}int k;while(~scanf("%d",&k)){if(k == 0) break;int ans = 0;while(k--){int x;scanf("%d",&x);ans ^= mex(x);}if(ans) puts("WIN");else puts("LOSE");}}return 0; }

總結(jié)

以上是生活随笔為你收集整理的HDU1524(博弈--有向无环图SG函数)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。