[题目来源]：POJ1364
[关键字]：差分约束系统
[题目大意]：给出一些不等式，判断能否同时成立。
//=====================================================================================================
[分析]：依据已给出的不等式构建差分约束系统，然后Bellman—Folyd判断是否有环。
[代码]：
View Code 1 program Project1; 2 type 3 rec = record 4 x, y, d: longint; 5 end; 6 var 7 n, m, st: longint; 8 d: array[0..300] of longint; 9 e: array[0..300] of rec;10 11 procedure make(i, x, y, d: longint);12 begin13 e[i].x := x;14 e[i].y := y;15 e[i].d := d;16 end;17 18 procedure init;19 var20 i, x, y, d: longint;21 ch, ch2: char;22 begin23 st := 9999999;24 for i := 1 to m do25 begin26 read(x,y);27 read(ch,ch2,ch,ch);28 readln(d);29 //writeln(x,' ',ch2,' ',y,' ',d);30 case ch2 of31 'g':make(i,x-1,x+y,d+1);32 'l':make(i,x+y,x-1,-d+1);33 end;34 if st > x-1 then st := x-1;35 end;36 end;37 38 function bellman:boolean;39 var40 i, j: longint;41 f: boolean;42 begin43 fillchar(d,sizeof(d),100);44 d[st] := 0;45 for i := 1 to n do46 begin47 f := true;48 for j := 1 to m do49 if d[e[j].y] < d[e[j].x]+e[j].d then50 begin51 d[e[j].y] := d[e[j].x]+e[j].d;52 f := false;53 end;54 if f then break;55 end;56 for i := 1 to m do57 if d[e[i].y] < d[e[i].x]+e[i].d then exit(false);58 exit(true);59 end;60 61 begin62 while 1 = 1 do63 begin64 read(n);65 if n = 0 then break;66 readln(m);67 init;68 if bellman then writeln('lamentable kingdom') else writeln('successful conspiracy');69 end;70 end.转载于:https://www.cnblogs.com/procedure2012/archive/2011/10/20/2218401.html
相关资源：垃圾分类数据集及代码