| ||||||||||
| 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