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