前言

每天一道C組題get√

題目

有一顆樹，只有一個(gè)樹根，Alice有M1塊石頭，Bob有M2塊石頭，Alice先移每個(gè)人輪流移動(dòng)石頭，誰先把自己的石頭全部移動(dòng)到樹根處就失敗了，輸出游戲勝者。

---

Input

　　輸入包含多組測(cè)試數(shù)據(jù)。
　　第一行輸入T(T<=10)表示測(cè)試數(shù)據(jù)組數(shù)。
　　接下來每組測(cè)試數(shù)據(jù)第一行輸入3個(gè)整數(shù)N(1<=N<=10000)，M1(1<=M1<=10000)，M2(1<=M2<=10000)，其中N表示樹的節(jié)點(diǎn)數(shù)。
　　接下來N-1行描述樹，每行包含兩個(gè)整數(shù)A和B(0<=A,B<=N-1)表示樹中有一條邊連接A,B兩點(diǎn)，注意0是樹根。
　　接下來一行M1個(gè)數(shù)，表示Alice的M1個(gè)石子的位置。
　　接下來一行M2個(gè)數(shù)，表示Bob的M2個(gè)石子的位置。

Output

對(duì)于每組測(cè)試數(shù)據(jù)，輸出贏家的名字。

Sample Input

2
3 1 1
0 1
2 0
1
2
3 2 1
0 1
1 2
2 2
2

Sample Output

Bob
Alice

---

解題思路

用SPFA求出每個(gè)點(diǎn)到根節(jié)點(diǎn)的最短路，然后加以判斷

---

代碼

#include<cstdio> #include<cstring> using namespace std; struct line{int last,next; }a[20001]; int f[10002],ls[10002],state[10002],t,n,m1,m2,dx,dy,w; int head,tail,s; bool b[10002]; void spfa()//找最短路 {memset(f,127/3,sizeof(f));head=0;tail=1;state[1]=1;b[1]=true;int q;f[1]=0;do{head=(head+2)%(n+1)-1;q=ls[state[head]];while (q!=0){if (f[state[head]]+1<f[a[q].last]){f[a[q].last]=f[state[head]]+1;if (!b[a[q].last]){b[a[q].last]=true;tail=(tail+2)%(n+1)-1;state[tail]=a[q].last;}}q=a[q].next;}b[state[head]]=false;}while (head!=tail); } int main() {scanf("%d",&t);for (int ti=1;ti<=t;ti++){memset(ls,0,sizeof(ls));scanf("%d%d%d",&n,&m1,&m2);w=0;for (int i=1;i<n;i++){scanf("%d%d",&dy,&dx);a[++w].last=dy+1;a[w].next=ls[dx+1];ls[dx+1]=w;a[++w].last=dx+1;a[w].next=ls[dy+1];ls[dy+1]=w;//建圖}spfa();s=0;for (int i=1;i<=m1;i++){scanf("%d",&dx);s+=f[dx+1];//累計(jì)}for (int i=1;i<=m2;i++){scanf("%d",&dx);s-=f[dx+1];//累計(jì)} if (s>0) printf("Alice\n");else printf("Bob\n");//判斷輸贏} }

總結(jié)

以上是生活随笔為你收集整理的jzoj1350-游戏（某C组）【SPFA，图，最短路】的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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