差分约束……
Program p2983;
var
n,m,i,j,p:longint;
c:char;
flag:boolean;
d:array[0..5000] of longint;
w:array[1..100100,1..3] of longint;
procedure relax(v,u,w:longint);
begin
if (d[v]>d[u]+w) then
begin
d[v]:=d[u]+w;
flag:=false;
end;
end;
procedure bellman_ford;
var
i,j,k:longint;
begin
flag:=true;
// w[i,3]=-1 w[i,2]-w[i,1]>0 ->w[i,1]-w[i,2]<0 ->w[i,1]-w[i,2]<=-1
// w[i,3]>-1 w[i,2]-w[i,1]=w[i,3] ->w[i,2]-w[i,1]<=w[i,3] w[i,1]-w[i,2]<=-w[i,3]
for k:=1 to n+1 do
begin
flag:=true;
for i:=1 to m do
begin
if w[i,3]=-1 then
begin
relax(w[i,1],w[i,2],-1);
end
else
begin
relax(w[i,2],w[i,1],w[i,3]);
relax(w[i,1],w[i,2],-w[i,3]);
end;
end;
if flag then break;
end;
if flag then writeln('Reliable')
else writeln('Unreliable');
end;
begin
while not seekeof do
begin
fillchar(d,sizeof(d),0);
readln(n,m);
for i:=1 to m do
begin
read(c);
if (c='p') or (c='P') then
begin
readln(w[i,1],w[i,2],w[i,3]);
end
else
begin
readln(w[i,1],w[i,2]);
w[i,3]:=-1;
end;
end;
bellman_ford;
end;
end.
分享到:
相关推荐
北大POJ2983-Is the Information Reliable【差分约束+优化Bellman】 解题报告+AC代码
北大POJ3253-POJ3253-Fence Repair【STL优先队列】 解题报告+AC代码
POJ水题集-----50道左右-----增加自信啊..
poj 1690 Your-Term-Project.md
poj 1240 Pre-Post-erous!.md
这是我个人写的POJ上2314题的Java实现,希望对喜欢ACM的人有帮助
西北工业大学-c语言-POJ-题目及答案-第七季.doc
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj题目分类--acmer做题极有用资源
用Java代码实现POJ(PKU)上题2494!
很有用的解题报告。。是acm初级提高的必备资料。。。。。
poj 1028 Web Navigation 的代码,已通过!
poj 1000 - 2000 部分题目 官方分类 poj 1000 - 2000 部分题目 官方分类
北大POJ3292-Semi-prime H-numbers 解题报告+AC代码
北大POJ2002-Squares 解题报告+AC代码
北大POJ1258-Agri-Net【Prim】 解题报告+AC代码
非常全的poj答案库 1164-1874 1000-4007
北大POJ2299-Ultra-QuickSort 解题报告+AC代码
POJ3211--Washing Clothes
业余爱好。所以,算法不一定好,CODING也不一定佳,效率不一定高,只是能通过online judge而已。