点击打开链接poj 2912
思路: 带权并查集
分析:
1 有n个小孩玩游戏,里面有一个入是裁判,剩下的人分为三组。现在我们既不知道裁判是谁也不知道分组的情况。现在n个小孩玩剪刀石头布,已知每组的小孩只会出同一种手势,问谁是裁判
2 题目说了输入=的时候说明是同一组,如果是<或>的时候说明是不同一组,那么根据食物链那一题的思路,我们设rank[x]表示x和根节点的关系,如果是=那么rank[x] = 0,如果是<则rank[x] = 1,否则为rank[x] = 2
3 剩下的就是怎么求最少几轮得到裁判的编号,要得出最后的裁判,也就是其他的人度不满足的最大的那一轮,因为那一轮过后就能确定裁判了
4 判断关系的时候,如果是不同的集合那就合并,否则判断是否有rank[x] == (rank[y]+val)%3
5 注意输入数据可能会有空格
代码:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int MAXN = 510;
struct Node{
int x;
int y;
int val;
};
Node node[4*MAXN];
int n , m;
int father[MAXN];
int rank[MAXN];
void init(int n){
memset(rank , 0 , sizeof(rank));
for(int i = 0 ; i < n ; i++)
father[i] = i;
}
int find(int x){
if(father[x] != x){
int fa = father[x];
father[x] = find(fa);
rank[x] = (rank[fa]+rank[x])%3;
}
return father[x];
}
void solve(){
int ans , step;
ans = -1;
step = 0;
for(int i = 0 ; i < n ; i++){
init(n);
int tmpStep = 0;
int j;
for(j = 0 ; j < m ; j++){
int x = node[j].x;
int y = node[j].y;
int fx = find(x);
int fy = find(y);
if(x == i || y == i)
continue;
if(fx != fy){
father[fx] = fy;
rank[fx] = (rank[y]+node[j].val-rank[x]+3)%3;
}
else{
if(rank[x] != (rank[y]+node[j].val)%3){
tmpStep = j+1;
break;
}
}
}
if(j == m){
if(ans == -1)
ans = i;
else{
puts("Can not determine");
return;
}
}
else
step = max(tmpStep , step);
}
if(ans == -1)
puts("Impossible");
else
printf("Player %d can be determined to be the judge after %d lines\n" , ans , step);
}
int main(){
char ch;
while(scanf("%d%d" , &n , &m) != EOF){
for(int i = 0 ; i < m ; i++){
scanf("%d" , &node[i].x);
while((ch = getchar()) == ' ');
scanf("%d" , &node[i].y);
if(ch == '=')
node[i].val = 0;
else if(ch == '<')
node[i].val = 1;
else
node[i].val = 2;
}
solve();
}
return 0;
}
分享到:
相关推荐
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
北大POJ2002-Squares 解题报告+AC代码
poj分类poj分类poj分类poj分类
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
POJ1048,加强版的约瑟夫问题 难度中等
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
Poj中一些题目的源代码,里面共有二十多道题目,OI
POJ2968代码有用,欢迎下载,POJ代码
解决算法问题 poj1082, poj1150, poj1180, poj1201, poj1222,代码完成所给题目要求。
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码