本文主要是介绍UVALive 6953 Digi Comp II（拓扑），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：
m个开关，n个球。每个开关有两个状态，左或右，左则滚到左边，右则滚到右边。每滚一个球状态则反转一次。问最后每个开关的状态是怎样的。
解题：
因为球数实在太多（10^18），一个一个模拟果断不行，而开关的最后状态只取决于滚过的球数和初始状态。所以计算出每个点球的流量并记录节点初始的状态即可。
注意：左右可以连同一个点！！！并且一开始不仅仅只有一为度数为零的点
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 500010
struct node
{ll l,r;ll num;ll in;bool status;
}id[maxn];
int main()
{long long n, m;while(~scanf("%lld%lld", &n, &m)){memset(id, 0, sizeof(id));char s[20];long long a, b;for(int i = 1; i <= m; i++){scanf("%s%lld%lld", s,&a,&b);id[i].l = a;id[i].r = b;if(s[0] == 'L')id[i].status = 1;elseid[i].status = 0;id[a].in++,id[b].in++;}id[1].num = n;queue<int>q;for(int i = 1; i <= m; i++){if(id[i].in == 0)q.push(i);}while(!q.empty()){int tmp = q.front();q.pop(); //printf("---%d %d\n",tmp,id[tmp].num);long long L = id[tmp].l, R = id[tmp].r;long long X = (id[tmp].num + 1)/2;long long Y = id[tmp].num - X;if(L || R){if(id[tmp].status)id[L].num += X,id[R].num += Y;else id[L].num += Y,id[R].num += X;id[L].in--,id[R].in--; if(L && id[L].in == 0)q.push(L);if(L != R &&R && id[R].in == 0)q.push(R);}}//for(int i = 1; i <= m; i++)//printf("%d %d\n",i,id[i].num);for(int i = 1; i <= m; i++){if(id[i].num % 2) id[i].status = !id[i].status;if(id[i].status)printf("L");else printf("R");}printf("\n");}return 0;
}
这篇关于UVALive 6953 Digi Comp II（拓扑）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
