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 |
并查集做的,总是output limit exceed.晕(附源码)#include <iostream> using namespace std; #define MAX 1001 int parent[MAX]; int dis[MAX]; int FindParent(int u) { int p = u; while(parent[p] != 0) p = parent[p]; return p; } bool check1(int u, int v, int w) { int i, j, p; int disu = 0 ,disv = 0; for(i = u; i ; i = parent[i]) { for(j = parent[v];j;j = parent[j]) if(i == j) goto End; } End: p = i; for(i = u; i != p; i = parent[i]) if(dis[u]) disu += dis[u]; else return true; for(i = v; i != p; i = parent[i]) if(dis[v]) disv += dis[v]; else return true; if(w == disv - disu) return true; else return false; } bool check2(int u, int v) { for(int i = parent[u]; i; i = parent[i]) if(v == i) return false; return true; } int main() { int N, M; int u, v, w; bool flag; while(scanf("%d%d", &N, &M)) { getchar(); flag = true; char ch; memset(parent, 0, sizeof(int)*(N+1)); memset(dis, -1, sizeof(int)*(N+1)); for(int i = 1; i <= M; ++i) { ch = getchar(); if(ch == 'P') { scanf("%d%d%d",&u, &v, &w); getchar(); if(FindParent(u) == FindParent(v)) { if(FindParent(u) == 0) { parent[v] = u; dis[v] = w; } else if(!check1(u,v,w)) flag = false; } else { parent[v] = u; dis[v] = w; } } else { scanf("%d%d",&u, &v); getchar(); if(FindParent(u) == FindParent(v)) { if(FindParent(u) == 0) { parent[v] = u; dis[v] = w; } else if(!check2(u,v)) flag = false; } else { parent[v] = u; dis[v] = 0; } } } cout << (flag?"Reliable":"Unreliable") << endl; } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator