| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
什么并查集,dfs就可以过(注意输入内面狗子描述的是自身的时猴要特殊处理!因为这个wa了一次)#include <iostream>
#include <stdio.h>
using namespace std;
int adj[1004][1004];
bool adjTF[1004][1004];
int adjNum[1004];
int used[1004];
int dui, cuo;
int zong = 0;
void init(int N){
for(int i = 1; i <= N; i++) {
adjNum[i] = 0;
used[i] = 0;
}
zong = 0;
}
void dfs(int i, bool tag){
used[i] = tag?1:-1;
if(tag) dui++;
else cuo++;
for(int j = 0; j < adjNum[i]; j++){
if(used[adj[i][j]] == 0){
bool t = (tag + adjTF[i][j])%2;
dfs(adj[i][j], t);
}
}
}
int main() {
while(1){
int N;
scanf("%d", &N);
if(N == 0) break;
init(N);
char fei1[32], fei2[4];
for(int i = 1; i <= N; i++){
int j;
char tf[15];
scanf("%s%d%s%s", fei1, &j, fei2, tf);
if(i != j){
adj[i][adjNum[i]] = j;
adj[j][adjNum[j]] = i;
if(tf[0] == 't'){
adjTF[i][adjNum[i]] = 0;
adjTF[j][adjNum[j]] = 0;
}
else{
adjTF[i][adjNum[i]] = 1;
adjTF[j][adjNum[j]] = 1;
}
adjNum[i]++;
adjNum[j]++;
}
else{
adj[i][adjNum[i]] = i;
if(tf[0] == 't'){
adjTF[i][adjNum[i]] = 0;
}
else{
adjTF[i][adjNum[i]] = 1;
}
adjNum[i]++;
}
}
for(int i = 1; i <= N; i++){
if(used[i] != 0) continue;
dui = 0;
cuo = 0;
dfs(i, 1);
if(dui > cuo) zong += dui;
else zong += cuo;
}
bool ok = 1;
for(int i = 1; i <= N; i++){
for(int j = 0; j < adjNum[i]; j++){
if(adjTF[i][j] && used[i] == used[adj[i][j]]){
ok = 0;
break;
}
if(!adjTF[i][j] && used[i] != used[adj[i][j]]){
ok = 0;
break;
}
}
}
if(ok){
printf("%d\n", zong);
}
else{
printf("Inconsistent\n");
}
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator