POJ 3169(带起点的拆分约束)

这次的拆分约束有明显的起点。

拆分等式 Xb-Xa<=C

     Xa-Xb<=-C

Program P3169;
const
   maxml=10000;
   maxn=1000;
var
   n,ml,md,i,j:longint;
   a,b:array[1..maxml,1..3] of longint;
   d:array[0..maxn] of longint;
   flag:boolean;
procedure relax(v,u,w:longint);
begin
   if d[v]>d[u]+w then
   begin
      d[v]:=d[u]+w;
      flag:=true;
   end;
end;
procedure bellman_ford;
var
   i,j,k:longint;
begin
   fillchar(d,sizeof(d),127);
   d[1]:=0;
   for k:=1 to ml+md do
   begin
      flag:=false;
      for i:=1 to ml do
      begin
         relax(a[i,2],a[i,1],a[i,3]);
      end;
      for i:=1 to md do
      begin
         relax(b[i,1],b[i,2],-b[i,3]);
      end;
      if not(flag) then break;
   end;
   if flag then writeln('-1')
   else if d[n]=2139062143 then writeln('-2')
   else writeln(d[n]);



end;
begin
   read(n,ml,md);
   for i:=1 to ml do
   begin
      read(a[i,1],a[i,2],a[i,3]);
   end;
   for i:=1 to md do
   begin
      read(b[i,1],b[i,2],b[i,3]);
   end;
   bellman_ford;
end.

POJ 2983(差分约束-有无解)

差分约束……

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.

POJ 1201 (差分约束)

1176 加权版 

……还是差分约束

Program P1201;
var
   n,i,j,minq,maxq:longint;
   d:array[-1..60000] of longint;
   w:array[1..60000,1..3] of longint;
   flag:boolean;
function min(a,b:longint):longint;
begin
   if a<b then exit(a) else exit(b);
end;
function max(a,b:longint):longint;
begin
   if a>b then exit(a) else exit(b);
end;

procedure relax(v,u,w:longint);
begin
   if (d[u]+w<d[v]) then
   begin
      d[v]:=d[u]+w;
      flag:=false;
   end;
end;
procedure bellman_ford;
var
   i,j,k:longint;
begin
   //d[w[i,2]] - d[w[i,1]-1]>=2 ->d[w[i,1]-1]-d[w[i,2]]<=-2
   //d[i]-d[i-1]<=1
   //d[i]-d[i-1]>=0 ->d[i-1]-d[i]<=0

   d[minq-1]:=0;
   while (true) do
   begin
      flag:=true;
//    for i:=minq to maxq do relax(i,minq-1,0);
      for i:=1 to n do relax(w[i,1]-1,w[i,2],-w[i,3]);
      for i:=minq to maxq do relax(i,i-1,1);
      for i:=maxq downto minq do relax(i-1,i,0);
      if flag then break;
   end;
end;
begin
   while not seekeof do
   begin
      minq:=maxlongint;  maxq:=0;
      fillchar(d,sizeof(d),0);
      read(n);
      for i:=1 to n do
      begin
         read(w[i,1],w[i,2],w[i,3]);
         minq:=min(minq,w[i,1]);
         maxq:=max(maxq,w[i,2]);
      end;
      bellman_ford;
      writeln(d[maxq]-d[minq-1]);
   end;
end.

POJ 1716 (差分约束)

差分约束……

Program P1716;
var
   n,i,j,minq,maxq:longint;
   d:array[-1..10000] of longint;
   w:array[1..30000,1..2] of longint;
   flag:boolean;
function min(a,b:longint):longint;
begin
   if a<b then exit(a) else exit(b);
end;
function max(a,b:longint):longint;
begin
   if a>b then exit(a) else exit(b);
end;

procedure relax(v,u,w:longint);
begin
   if (d[u]+w<d[v]) then
   begin
      d[v]:=d[u]+w;
      flag:=false;
   end;
end;
procedure bellman_ford;
var
   i,j,k:longint;
begin
   //d[w[i,2]] - d[w[i,1]-1]>=2 ->d[w[i,1]-1]-d[w[i,2]]<=-2
   //d[i]-d[i-1]<=1
   //d[i]-d[i-1]>=0 ->d[i-1]-d[i]<=0

   d[minq-1]:=0;
   while (true) do
   begin
      flag:=true;
//    for i:=minq to maxq do relax(i,minq-1,0);
      for i:=1 to n do relax(w[i,1]-1,w[i,2],-2);
      for i:=minq to maxq do relax(i,i-1,1);
      for i:=maxq downto minq do relax(i-1,i,0);
      if flag then break;
   end;
end;
begin
   while not seekeof do
   begin
      minq:=maxlongint;  maxq:=0;
      fillchar(d,sizeof(d),0);
      read(n);
      for i:=1 to n do
      begin
         read(w[i,1],w[i,2]);
         minq:=min(minq,w[i,1]);
         maxq:=max(maxq,w[i,2]);
      end;
      bellman_ford;
      writeln(d[maxq]-d[minq-1]);
   end;
end.