Illyasviel的圖游戲

除了1號點和n號點每個點度數(shù)小于等于2，因此1 到 n 的所有簡單路徑互不相交。

在結(jié)束游戲前的最后一步一定是剩下一條 1 到 n 的路徑，并且路徑上的權(quán)值全都是1。

游戲總步數(shù)確定，如果剩下的最后一條路徑確定了，先后手的勝負(fù)就確定了。

那么雙方的策略就使盡可能使最后留下的路徑是使自己必勝的路徑，即盡可能切斷使對方必勝的路徑。

如果先手Alice想贏：

若 初始時圖中所有邊的邊權(quán)和為奇數(shù)：那么他一定要使剩下的最后一條路徑有偶數(shù)條邊（是邊數(shù)，不是邊權(quán)和），即他要在Bob把有偶數(shù)條邊的路徑拆完前把有奇數(shù)條邊的路徑拆完；

若 初始時圖中所有邊的邊權(quán)和為偶數(shù)：那么他一定要使剩下的最后一條路徑有奇數(shù)條邊（是邊數(shù)，不是邊權(quán)和），即他要在Bob把有奇數(shù)條邊的路徑拆完前把有偶數(shù)條邊的路徑拆完；

切斷一條路徑需要的步數(shù)是這條路徑上的權(quán)值的最小值。我們只需要比較雙方切斷對方必勝的路徑所需要的步數(shù)即可。

#include<iostream> #include<cstdio> using namespace std; typedef long long ll; const int N=1e5+10; const int M=150000; const ll inf=1e9+7; struct Edge{int v,w,nxt; }edge[M<<1]; int cnt,head[N],n,m; ll sum,st[2];//st[0/1]:拆完有偶數(shù)/奇數(shù)條邊的路徑所需步數(shù) void add(int u,int v,int w){edge[++cnt].v=v;edge[cnt].w=w;edge[cnt].nxt=head[u];head[u]=cnt; } void dfs(int u,int fa,ll minn,bool type){//type=0:路徑有偶數(shù)條邊，type=1:路徑有奇數(shù)條邊 if(u==n){st[type]+=minn;return;}for(int i=head[u];i;i=edge[i].nxt){int v=edge[i].v;if(v==fa) continue;dfs(v,u,min(minn,1ll*edge[i].w),type^1);} } int main(){scanf("%d%d",&n,&m);for(int i=1;i<=m;i++){int u,v,w;scanf("%d%d%d",&u,&v,&w);add(u,v,w);add(v,u,w);sum+=1ll*w;}dfs(1,0,inf,0);if(sum&1){if(st[0]>=st[1]) printf("Yes\n");else printf("No\n");}else{if(st[0]<=st[1]) printf("Yes\n");else printf("No\n");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的[XSY]Illyasviel的图游戏(博弈论)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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