Posted on 2010-03-23 21:45
Uriel 閱讀(386)
評(píng)論(0) 編輯 收藏 引用 所屬分類:
POJ 、
圖論
圖論一直一無(wú)所知，說(shuō)著要開(kāi)始看要開(kāi)始看因?yàn)閯e的很多東西都很菜就一直拖著沒(méi)看，目前只會(huì)Prime，Dijkstra，Kruskal半會(huì)，F(xiàn)loyd，最近幾天剛看的差分約束，前兩道建圖都參考了別人的代碼，后來(lái)的幾道又每次都因?yàn)檫@個(gè)那個(gè)原因WA幾次，1899這題是題沒(méi)看清，以為邊是1000，RE好幾次。。用Bellman_Ford水的，所以沒(méi)有Discuss里說(shuō)的SPFA會(huì)碰到的那些問(wèn)題。。
差不多算是把網(wǎng)上搜到的POJ幾題差分約束的題都A了，這題是最后一道，發(fā)個(gè)代碼留個(gè)紀(jì)念~~
/**//*
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;
}