http://poj.org/problem?id=2983
题目大意：
星际大战开始了。你购买了情报，需要判断它的准确性。已知地方的根据地在由南向北排成一条直线。P A B X，表示A在B北面距离X光年的地方，另一种是V A B，表示只知道A在B的北面至少1光年的地方。
思路：
可转化为差分约束。
对于P A B X来说 可以记做： X>= A-B >=X ， (因为他们相距X光年，我们取北边为正方向）
对于V A B ，可以记做 A-B>=1
然后老样子差分约束。记得建立一个连接所有顶点的超级顶点来保证图的连通性~
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int MAXN=1000+10;
const int MAXM=200000+1000;
const int INF=-9999999;
struct edge
{
int to;
int val;
int next;
}e[MAXM];
int head[MAXN],dis[MAXN],len,n,m;
void add(int from,int to,int val)
{
e[len].to=to;
e[len].val=val;
e[len].next=head[from];
head[from]=len++;
}
bool spfa()
{
int start=n+1;
for(int i=1;i<=n;i++)
dis[i]=INF;
bool vis[MAXN]={0};
int cnt[MAXN]={0};
deque<int> q;
q.push_back(start);
vis[start]=1;
cnt[start]=1;
dis[start]=0;
while(!q.empty())
{
int cur=q.front();
q.pop_front();
vis[cur]=false;
for(int i=head[cur];i!=-1;i=e[i].next)
{
int id=e[i].to;
if(dis[id] < dis[cur] + e[i].val)
{
dis[id]=dis[cur] + e[i].val;
if(!vis[id])
{
if(++cnt[id] > n)
return true;
vis[id]=true;
if(!q.empty() && dis[id] > dis[q.front()])
q.push_back(id);
else
q.push_front(id);
}
}
}
}
return false;
}
int main()
{
while(~scanf("%d%d",&n,&m))
{
memset(head,-1,sizeof(head));
len=0;
for(int i=0;i<m;i++)
{
char cmd[5];
int from,to,val;
scanf("%s",cmd);
if(cmd[0]==‘P‘)
{
scanf("%d%d%d",&from,&to,&val);
add(from,to,-val);
add(to,from,val);
}
else
{
scanf("%d%d",&from,&to);
add(to,from,1);
}
}
for(int i=1;i<=n;i++)
add(n+1,i,0);
if(spfa())
puts("Unreliable");
else
puts("Reliable");
}
return 0;
}