Posted on 2010-03-23 21:45
Uriel 阅读(385)
评论(0) 编辑 收藏 引用 所属分类:
POJ 、
图论
图论一直一无所知，说着要开始看要开始看因为别的很多东西都很菜就一直拖着没看，目前只会Prime，Dijkstra，Kruskal半会，Floyd，最近几天刚看的差分约束，前两道建图都参考了别人的代码，后来的几道又每次都因为这个那个原因WA几次，1899这题是题没看清，以为边是1000，RE好几次。。用Bellman_Ford水的，所以没有Discuss里说的SPFA会碰到的那些问题。。
差不多算是把网上搜到的POJ几题差分约束的题都A了，这题是最后一道，发个代码留个纪念~~
/**//*
Problem: 2983 User: Uriel
Memory: 2520K Time: 454MS
Language: C++ Result: Accepted
*/
#include<stdio.h>
#include<stdlib.h>
#define INF 100000000
struct Edge
{
int s,e,len;
};
Edge E[200010];
int n,m,edge_cnt,dis[2010];
void add_edge(int a,int b,int c)
{
E[edge_cnt].s=a;
E[edge_cnt].e=b;
E[edge_cnt].len=c;
}
bool Bellman_Ford(int s)
{
int i,j;
bool ok;
for(i=0;i<=n;i++)dis[i]=INF;
for(i=0;i<n;i++)
{
ok=true;
for(j=1;j<=edge_cnt;j++)
{
if(dis[E[j].e]>dis[E[j].s]+E[j].len)
{
ok=false;
dis[E[j].e]=dis[E[j].s]+E[j].len;
}
}
if(ok)break;
}
for(i=1;i<=edge_cnt;i++)
{
if(dis[E[i].e]>dis[E[i].s]+E[i].len)return false;
}
return true;
}
int main()
{
int a,b,x;
char ch;
while(scanf("%d %d",&n,&m)!=EOF)
{
edge_cnt=1;
while(m--)
{
getchar();
ch=getchar();
if(ch=='P')
{
scanf("%d %d %d",&a,&b,&x);
add_edge(a,b,-x);
edge_cnt++;
add_edge(b,a,x);
edge_cnt++;
}
else
{
scanf("%d %d",&a,&b);
add_edge(a,b,-1);
edge_cnt++;
}
}
if(Bellman_Ford(0))
{
printf("Reliable\n");
}
else
{
printf("Unreliable\n");
}
}
system("PAUSE");
return 0;
}