做网站需要哪些硬件,专业做甜点的网站,韩韩良品只做性价比网站下载,wordpress主题开发框架前言
每天一道C组题get√
题目
有一颗树#xff0c;只有一个树根#xff0c;Alice有M1块石头#xff0c;Bob有M2块石头#xff0c;Alice先移每个人轮流移动石头#xff0c;谁先把自己的石头全部移动到树根处就失败了#xff0c;输出游戏胜者。 Input 输入包含多组测试…前言
每天一道C组题get√
题目
有一颗树只有一个树根Alice有M1块石头Bob有M2块石头Alice先移每个人轮流移动石头谁先把自己的石头全部移动到树根处就失败了输出游戏胜者。 Input 输入包含多组测试数据。 第一行输入T(T10)表示测试数据组数。 接下来每组测试数据第一行输入3个整数N(1N10000)M1(1M110000)M2(1M210000)其中N表示树的节点数。 接下来N-1行描述树每行包含两个整数A和B(0A,BN-1)表示树中有一条边连接A,B两点注意0是树根。 接下来一行M1个数表示Alice的M1个石子的位置。 接下来一行M2个数表示Bob的M2个石子的位置。
Output
对于每组测试数据输出赢家的名字。
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求出每个点到根节点的最短路然后加以判断 代码
#includecstdio
#includecstring
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));head0;tail1;state[1]1;b[1]true;int q;f[1]0;do{head(head2)%(n1)-1;qls[state[head]];while (q!0){if (f[state[head]]1f[a[q].last]){f[a[q].last]f[state[head]]1;if (!b[a[q].last]){b[a[q].last]true;tail(tail2)%(n1)-1;state[tail]a[q].last;}}qa[q].next;}b[state[head]]false;}while (head!tail);
}
int main()
{scanf(%d,t);for (int ti1;tit;ti){memset(ls,0,sizeof(ls));scanf(%d%d%d,n,m1,m2);w0;for (int i1;in;i){scanf(%d%d,dy,dx);a[w].lastdy1;a[w].nextls[dx1];ls[dx1]w;a[w].lastdx1;a[w].nextls[dy1];ls[dy1]w;//建图}spfa();s0;for (int i1;im1;i){scanf(%d,dx);sf[dx1];//累计}for (int i1;im2;i){scanf(%d,dx);s-f[dx1];//累计} if (s0) printf(Alice\n);else printf(Bob\n);//判断输赢}
}
