题目链接: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 ;
}

最新文章

  1. Node.js 教程 03 - 创建HTTP服务器
  2. Python之str()与repr()的区别
  3. Android ui 测试课堂笔记
  4. 简述ES5 ES6
  5. POJ 2457 Part Acquisition
  6. android Activity基类通用方法
  7. redis 的安装
  8. linux系统安装对硬件有什么要求
  9. Linux系统及应用问题分析排查工具
  10. java遍历map方法
  11. J2EE之ANT
  12. C++类成员常量
  13. 浅析js模板引擎
  14. STM32F10X SPI操作flash MX25L64读写数据(转)
  15. Jvm 中的 重排序、主存、原子操作
  16. selenium 添加动态隧道代理
  17. 【洛谷P3369】【模板】普通平衡树题解
  18. 133. leetcode-Clone Graph
  19. 压缩文件破解rarcrack-支持格式zip,rar和7z
  20. 由于想要实现下载的文件可以进行选择,而不是通过&lt;a&gt;标签写死下载文件的参数,所以一直想要使用JFinal结合ajax实现文件下载,但是ajax实现的文件下载并不能触发浏览器的下载文件弹出框,这里通过模拟表单提交实现同样的效果。

热门文章

  1. CentOS下rpm指令和yum指令详解
  2. 真想用c#开发个 wp五笔输入法。。。奈何网上资料太少,源码都是c++写的。求大神指点!!!
  3. 如何强制关闭Tomcat
  4. mysql connection不断增加
  5. 拼凑sql语句另外一个方法
  6. 在你开发完brew应用之后 ,你又如果将brew应用由编译成可以部署到brew真机上的程序包呢
  7. KAFKA安装+配置详解+常用操作+监控
  8. vs2013\2015-UML
  9. CreateEvent和SetEvent及WaitForSingleObject的使用方法
  10. javascript--枚举算法实现