POJ2912 Rochambeau —— 种类并查集 + 枚举
题目链接:http://poj.org/problem?id=2912
Time Limit: 5000MS | Memory Limit: 65536K | |
Total Submissions: 3663 | Accepted: 1285 |
Description
N children are playing Rochambeau (scissors-rock-cloth) game with you. One of them is the judge. The rest children are divided into three groups (it is possible that some group is empty). You don’t know who is the judge, or how the children are grouped. Then the children start playing Rochambeau game for M rounds. Each round two children are arbitrarily selected to play Rochambeau for one once, and you will be told the outcome while not knowing which gesture the children presented. It is known that the children in the same group would present the same gesture (hence, two children in the same group always get draw when playing) and different groups for different gestures. The judge would present gesture randomly each time, hence no one knows what gesture the judge would present. Can you guess who is the judge after after the game ends? If you can, after how many rounds can you find out the judge at the earliest?
Input
Input contains multiple test cases. Each test case starts with two integers N and M (1 ≤ N ≤ 500, 0 ≤ M ≤ 2,000) in one line, which are the number of children and the number of rounds. Following are M lines, each line contains two integers in [0, N) separated by one symbol. The two integers are the IDs of the two children selected to play Rochambeau for this round. The symbol may be “=”, “>” or “<”, referring to a draw, that first child wins and that second child wins respectively.
Output
There is only one line for each test case. If the judge can be found, print the ID of the judge, and the least number of rounds after which the judge can be uniquely determined. If the judge can not be found, or the outcomes of the M rounds of game are inconsistent, print the corresponding message.
Sample Input
3 3
0<1
1<2
2<0
3 5
0<1
0>1
1<2
1>2
0<2
4 4
0<1
0>1
2<3
2>3
1 0
Sample Output
Can not determine
Player 1 can be determined to be the judge after 4 lines
Impossible
Player 0 can be determined to be the judge after 0 lines
Source
Chen, Shixi (xreborner) living in http://fairyair.yeah.net/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
#define ms(a,b) memset((a),(b),sizeof((a)))
using namespace std;
typedef long long LL;
const double EPS = 1e-;
const int INF = 2e9;
const LL LNF = 2e18;
const int MAXN = 1e3+; int n, m;
int fa[MAXN], r[MAXN];
struct node
{
int u, v, w;
}a[]; int find(int x)
{
if(fa[x]==-) return x;
int pre = find(fa[x]);
r[x] = (r[x]+r[fa[x]])%;
return fa[x] = pre;
} bool Union(int u, int v, int w)
{
int fu = find(u);
int fv = find(v);
if(fu==fv)
return ((-w+r[u])%!=r[v]); fa[fu] = fv;
r[fu] = (-r[u]+w+r[v])%;
return false;
} int main()
{
while(scanf("%d%d", &n, &m)!=EOF)
{
for(int i = ; i<=m; i++)
{
char ch;
scanf("%d%c%d", &a[i].u, &ch, &a[i].v);
if(ch=='=') a[i].w = ;
if(ch=='<') a[i].w = ;
if(ch=='>') a[i].w = ;
} int judge, index = , cnt = ; //judge为裁判的下标, index为找到裁判时的下标, cnt为可能是裁判的人的个数。
for(int k = ; k<n; k++) //枚举每一个人作为裁判
{
bool flag = true;
memset(fa, -, sizeof(fa));
memset(r, , sizeof(r));
for(int i = ; i<=m; i++)
{
int u = a[i].u, v = a[i].v, w = a[i].w; //其中一个人是“裁判”, 则不作处理
if(u==k || v==k) continue; if(Union(u, v, w)) //出现冲突,排除这个人是裁判
{
/**找到裁判时的下标,取所有发生冲突时,下标的最大值。为什么?
当排除完其他人都不是裁判时,裁判是谁就自然显露出来了 **/
index = max(index, i);
flag = false;
break;
}
} if(flag) //如果跳过了k后,其他人的关系都不会发生冲突, 那么k就有可能是裁判
{
judge = k;
cnt++; //更新个数
}
} if(cnt==) //可能是裁判的人的个数为0:谁都不可能是裁判
printf("Impossible\n");
else if(cnt>) //可能是裁判的人的个数大于1:不能确定谁是裁判
printf("Can not determine\n");
else //可能是裁判的人的个数等于1:这个人就是裁判
printf("Player %d can be determined to be the judge after %d lines\n", judge, index);
}
}
最新文章
- java JVM
- C#如何获取CPU处理器核心数量 z
- sql server 2014预览版发布
- urllib3 PoolManager
- SqlBulkCopy大批量数据插入到sql表中
- 通过从代码层面分析Linux内核启动来探知操作系统的启动过程
- Dictionary<;Key,Value>;的用法
- 我的第一个 Rails 站点:极简优雅的笔记工具-Raysnote
- jquery事件之event.target用法详解
- Build FFmpeg for iOS
- require.js模块化写法
- Codeforces Round #401 (Div. 2)
- ArcGIS API for JavaScript 入门教程[2] 授人以渔
- filebeat_config
- Java中ArrayList的删除元素总结
- python网络编程(三)
- 使用开源的工具解析erspan流量
- 201621123018《java程序设计》第11周作业总结
- 在Jenkins中配置执行远程shell命令(转)
- 一种模块化开发的目录结构和部署tips
热门文章
- 一些简单的JavaScript的方法
- HackerRank# Wet Shark and Two Subsequences
- bzoj 2802 [Poi2012]Warehouse Store STL
- google play上获取apk文件
- 最近公共祖先(Least Common Ancestors)
- HDU 5667 Sequence
- zoj4028 LIS
- Ultra-QuickSort--POJ2299(归并排序求逆序数对)
- [Bzoj3131][Sdoi2013]淘金(数位dp)(优先队列)
- Go --- 设计模式(模板模式)