题目链接:poj 2912 Rochambeau
题目大意:n个小伙伴进行猜拳有戏,除了一个比较聪明的家伙以外,其他人只会出单一的一种,给出m中猜拳的结果,要求找出那个比较聪明的小伙伴序号,并且输出在第几次猜拳可以确定。(注意<,>,=前后可能有空格)
解题思路:枚举每个人作为最聪明的家伙,如果将他所有的关系都剔除后还有矛盾的情况,则说明他不是要找的那个家伙,如果存在两个以上,则是不可能的。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 2005;
const int M = 505;
int n, m, f[M], r[N];
int u[N], v[N], s[N], vis[N];
int getfar(int x) {
if (x != f[x]) {
int t = f[x];
f[x] = getfar(f[x]);
r[x] = (r[x] + r[t])%3;
}
return f[x];
}
void read () {
char ch;
for (int i = 0; i < m; i++) {
scanf("%d", &u[i]);
while ((ch = getchar()) == ' ') ;
scanf("%d", &v[i]);
if (ch == '=')
s[i] = 0;
else if (ch == '<')
s[i] = 1;
else
s[i] = 2;
}
}
void init () {
for (int i = 0; i <= n; i++)
f[i] = i;
memset(r, 0, sizeof(r));
}
void solve () {
int ans = -1, rec = 0;
for (int i = 0; i < n; i++) {
init ();
int j, tmp = 0;
for (j = 0; j < m; j++) {
int a = u[j];
int b = v[j];
if (a == i || b == i) continue;
int p = getfar(a);
int q = getfar(b);
if (p == q) {
if (r[a] != (r[b] + s[j])%3) {
tmp = j + 1;
break;
}
} else {
f[p] = q;
r[p] = (r[b] + s[j] - r[a] + 3) % 3;
}
}
if (j == m) {
if (ans == -1) {
ans = i;
} else {
printf("Can not determine\n");
return;
}
} else
rec = max(rec, tmp);
}
if (ans == -1)
printf("Impossible\n");
else
printf("Player %d can be determined to be the judge after %d lines\n" , ans , rec);
}
int main () {
while (scanf("%d%d", &n, &m) == 2) {
read ();
solve ();
}
return 0;
}
分享到:
相关推荐
poj2492 A Bug's Life并查集应用的扩展,希望可以给大家带来用处
POJ 1988 并查集。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
NULL 博文链接:https://128kj.iteye.com/blog/1750462
poj 1611 The Suspects 代码 并查集的应用
这份代码用C++实现了经典算法并查集,来源于poj题目1182
数据结构并查集的相关资料,包括几篇并查集的论文,还有POJ上面几道关于并查集的题目的源代码
西北工业大学POJ试题C++答案代码+课程设计
北大POJ1207-The 3n + 1 problem 解题报告+AC代码
并查集基础 acm 算法 poj oi 并查集基础.ppt
POJ1089 并查集可以解决 并查集加路径压缩
2505 2521 2538 2546 2551 2590 2593 2601 2665 2680 2739 2752 2761 2762 2777 2800 2891 2893 2992 3030 3041 3132 3159 3187 3204 3270 3277 3281 3297 3321 3414 3436 3461 3650 3663 3664 3672 3740
北大POJ初级-简单搜索 解题报告+AC代码
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
1011,1012,1013,1014,1015,1017,1026,1028,1032,1035,1041,1046,1129 1149 1154 1165 1182 1185 1190 1191 1201 1251 1273 1275 1276 1286 1322 1338 1363 1364 1401 1456 1459 1564 1579 1637 1657 1658 ...
北大POJ3009-Curling 2.0【DFS+Vector+回溯+剪枝】 解题报告+AC代码
POJ-2870 Light Up + DFS(1级DFS+1级DFS) + Python - 思维导图 链接:https://blog.csdn.net/xxdragon126/article/details/122095922?spm=1001.2014.3001.5501
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
北大POJ1159-Palindrome 解题报告+AC代码
北大POJ3026-Borg Maze【BFS+Prim】 解题报告+AC代码
北大POJ初级-所有题目AC代码+解题报告