poj 2912 Rochambeau(権力と捜査+暴力)
2694 ワード
テーマ:poj 2912 Rochambeau(権力と調査集+暴力)
テーマは3つのチームと1つの審判を与えて、この3つのチームは審判と一緒にハサミの石布を游んで、それから各チームが同じものを出さなければならないことを規定して、審判だけが自由に出すことができます.そして関係を与え、x>yはxがyに勝つことを表し、x问题の考え方:この问题の重点は裁判が中で関系を乱すことができて、しかもn*mは100000で、完全に暴力することができます.iが審判であると仮定するたびに、審判との関係は無視されます.審判は任意の動作をすることができるからです.そして残りを組み合わせて、その中で矛盾が出てきたら、これは審判ではないことを説明し、いくつかの矛盾を記録して、使うことができます.そしてこのように判断した後、審判が一人もいなければ、このような関係は存在しないことを説明します.複数の審判が審判が唯一ではないと説明した場合、記録したばかりの矛盾が現れた位置を使う必要がある.i番目が審判であると判断すると、他は審判ではないことを示し、他が審判でなければiが審判であると断定することはできないので、矛盾が生じる最大の位置を取れば審判の位置を確定することになる.
注意:この問題は審判を判断するたびに1回実行し、セットを調べる必要があります.毎回初期化しなければならないことを覚えておいてください.
コード:
テーマは3つのチームと1つの審判を与えて、この3つのチームは審判と一緒にハサミの石布を游んで、それから各チームが同じものを出さなければならないことを規定して、審判だけが自由に出すことができます.そして関係を与え、x>yはxがyに勝つことを表し、x
注意:この問題は審判を判断するたびに1回実行し、セットを調べる必要があります.毎回初期化しなければならないことを覚えておいてください.
コード:
#include <stdio.h>
#include <string.h>
const int N = 505;
const int M = 2005;
int n, m, f[N], c[N];
int r[M][2], vis[M];
void init () {
for (int i = 0; i < n; i++) {
f[i] = i;
c[i] = 0;
}
}
int getfather (int x) {
if ( x != f[x] ) {
int t = f[x];
f[x] = getfather(f[x]);
c[x] = (c[x] + c[t] ) % 3;
}
return f[x];
}
int main () {
char ch;
int x, y;
int flc, count, max, judge;
while (scanf ("%d%d", &n, &m) != EOF) {
// init ();
count = 0;
max = 0;
memset (vis, 0, sizeof (vis));
for (int i = 0; i < m; i++) {
scanf ("%d", &x);
while (scanf ("%c", &ch) , ch == ' ');
scanf ("%d", &y);
if (ch == '<') {
r[i][0] = x;
r[i][1] = y;
} else if (ch == '>') {
r[i][0] = y;
r[i][1] = x;
} else {
r[i][0] = x;
r[i][1] = y;
vis[i] = 1;
}
}
for (int i = 0; i < n; i++) {
init ();
flc = 0;
for (int j = 0; j < m; j++) {
if (r[j][0] == i || r[j][1] == i)
continue;
int p = getfather (r[j][0]);
int q = getfather (r[j][1]);
int d = (vis[j] + 1) % 2;
if (p != q) {
f[q] = p;
c[q] = (c[r[j][0]] - c[r[j][1]] + 3 + d) % 3;
} else {
if ( (c[r[j][0]] + d) % 3 != c[r[j][1]]) {
flc = j + 1;
if (max < flc)
max = flc;
break;
}
}
}
if (!flc)
count++;
if ( !flc && count == 1) {
judge = i;
// printf ("%d
", i);
}
}
if (!count)
printf ("Impossible
");
else if (count > 1)
printf ("Can not determine
");
else
printf ("Player %d can be determined to be the judge after %d lines
", judge, max);
}
return 0;
}