Rochambeau---poj2912||zoj2751(并查集类似于食物链)

题目链接:http://poj.org/problem?id=2912 

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1751

题意:有n个人玩石头剪刀布,所以会产生石头>剪刀,剪刀>布,布>石头,所以就产生了和食物链那题一样的关系;

枚举+关系并查集,枚举每个小孩为judge时的情况,若当前枚举情况下每个round都是正确的,则当前枚举编号可能是judge。

若只找到一个judge的可能,即为输出。若有多个就不确定了;

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <stack>
#include <map>
#include <vector>
using namespace std;
typedef long long LL;
#define N 2520
#define met(a, b) memset(a, b, sizeof(a)) int f[N], r[N], wrong[N]; int Find(int x)
{
int k = f[x];
if(x!=f[x])
{
f[x] = Find(f[x]);
r[x] = (r[x]+r[k])%;
}
return f[x];
} struct node
{
int x, y, op;
}a[N];
int main()
{
int n, m;
while(scanf("%d %d", &n, &m)!=EOF)
{
met(a, ); for(int i=; i<=m; i++)
{
char ch;
scanf("%d%c%d", &a[i].x, &ch, &a[i].y);
if(ch == '=') a[i].op = ;
if(ch == '>') a[i].op = ;
if(ch == '<') a[i].op = ;
} for(int i=; i<n; i++)///枚举裁判;
{
for(int j=; j<n; j++)
f[j] = j, r[j] = ; wrong[i] = ;///第i个人当裁判的时候在哪产生矛盾;
for(int j=; j<=m; j++)
{
if(a[j].x == i || a[j].y == i)continue;
int x = a[j].x, y = a[j].y; int px = Find(x);
int py = Find(y); if(px != py)
{
f[px] = py;
r[px] = (r[y] + a[j].op - r[x] + )%;
}
else if(px == py && (r[y]+a[j].op)% != r[x])
{
wrong[i] = j;
break;
}
}
}
int judge = , ans = , Index;
for(int i=; i<n; i++)
{
if(wrong[i] == )
{
judge++;
Index = i;
}
ans = max(wrong[i], ans);///当其他的情况矛盾了,那么就是确定结果的时候;
}
if(judge == ) printf("Player %d can be determined to be the judge after %d lines\n", Index, ans);
else if(judge == ) printf("Impossible\n");///没有产生;
else printf("Can not determine\n");///产生的不止一个,就是不确定;
}
return ;
}
上一篇:【MongoDB】MongoDB与项目搭配启动进程


下一篇:Android仿QQ微信开场导航以及登陆界面