題目：http://poj.org/problem?id=2983
Is the Information Reliable?
Time Limit: 3000MS Memory Limit: 131072K
Total Submissions: 12535 Accepted: 3943
Description
The galaxy war between the Empire Draco and the Commonwealth of Zibu broke out 3 years ago. Draco established a line of defense called Grot. Grot is a straight line with N defense stations. Because of the cooperation of the stations, Zibu’s Marine Glory cannot march any further but stay outside the line.
A mystery Information Group X benefits form selling information to both sides of the war. Today you the administrator of Zibu’s Intelligence Department got a piece of information about Grot’s defense stations’ arrangement from Information Group X. Your task is to determine whether the information is reliable.
The information consists of M tips. Each tip is either precise or vague.
Precise tip is in the form of P A B X, means defense station A is X light-years north of defense station B.
Vague tip is in the form of V A B, means defense station A is in the north of defense station B, at least 1 light-year, but the precise distance is unknown.
Input
There are several test cases in the input. Each test case starts with two integers N (0 < N ≤ 1000) and M (1 ≤ M ≤ 100000).The next M line each describe a tip, either in precise form or vague form.
Output
Output one line for each test case in the input. Output “Reliable” if It is possible to arrange N defense stations satisfying all the M tips, otherwise output “Unreliable”.
Sample Input
3 4
P 1 2 1
P 2 3 1
V 1 3
P 1 3 1
5 5
V 1 2
V 2 3
V 3 4
V 4 5
V 3 5
Sample Output
Unreliable
Reliable
Source
POJ Monthly–2006.08.27, Dagger
題意：n個點，告知m個a,b間（有向）路徑長度或路徑長度>=1；求信息有誤否。
思路：差分束縛系統，建邊
1.a-b>=c b-a>=-c
2.a-b>=1;
‘>=’建最小邊，spfa最長路，更新次數>=n—->有環—》false；
代碼：
#include<iostream>
#include<stdio.h>
#include<vector>
#include<string.h>
#include<queue>
using namespace std;
int n,m;
char s[3];
int aa,bb,cc;
int tot;
struct nod{
int x,v;
nod(int xx,int vv)
{
x=xx,v=vv;
}nod(){}
};
vector<nod> lin[1005];
int vis[1005],d[1005];
int cnt[1005];
queue<int> Q;
bool spfa()
{
Q.push(0);
d[0]=0;
vis[0]=1;
while(!Q.empty())
{
int now=Q.front();
Q.pop();
vis[now]=0;
for(int i=0;i<lin[now].size();i++)
{
int v=lin[now][i].x;
int vv=lin[now][i].v;
if(d[v]==-1||d[v]<d[now]+vv)
{
d[v]=d[now]+vv;
cnt[v]++;
if(cnt[v]>n)
{
return false;
}
if(!vis[v])
{
vis[v]=1;
Q.push(v);
}
}
}
}
return 1;
}
int main()
{
while(scanf("%d%d",&n,&m)!=EOF)
{
for(int i=1;i<=n;i++)
{
lin[i].clear();
d[i]=-1;
vis[i]=0;
cnt[i]=0;
}
for(int i=1;i<=m;i++)
{
scanf("%s",s);
if(s[0]=='P')
{
scanf("%d%d%d",&aa,&bb,&cc);
lin[aa].push_back(nod(bb,cc));
lin[bb].push_back(nod(aa,-cc));
}
else if(s[0]=='V')
{
scanf("%d%d",&aa,&bb);
lin[aa].push_back(nod(bb,1));
}
}
for(int i=1;i<n;i++)
{
lin[0].push_back(nod(i,0));
}
if(!spfa())
printf("Unreliable\n");
else printf("Reliable\n");
}
}
上一篇 storm 學習教程
下一篇 R語言動量交易策略分析
程序員人生，我編程，我富裕，記住wfuyu網，php教程，php學習，php手冊，CMS模版制作
聲明：本站大部分內容是作者原創，少部分收集于互聯網供大家一起學習，原版權很多不明，如有侵權請聯系本站，謝謝！
粵ICP備14040726號-1?? 2015-2020 程序員人生 版權所有
