program prison;
var f:array[1..20000,1..20000] of longint;
     n,m,i,j,k,max,max1,maxi,maxj:integer;
     t:boolean;
procedure recor(x,y:integer);
begin
   maxi:=x;
   maxj:=y;
   max1:=abs(f[x,y]);
end;
procedure mark(x,y,z:integer);
begin
   if f[y,x]<f[z,x] then f[y,x]:=-f[y,x] else f[z,x]:=-f[z,x];
end;
begin
   readln(n,m);
   for i:=1 to m do
     begin
       read(j,k);
       readln(f[j,k]);
     end;
   repeat
     max1:=0;
     t:=true;
     for i:=1 to n do
       for j:=i+1 to n do
         begin
           if max1<abs(f[i,j]) then recor(i,j);
           if f[i,j]>0 then t:=false;
         end;
     if f[maxi,maxj]<0 then max1:=f[maxi,maxj] else f[maxi,maxj]:=0;
     for i:=maxj+1 to n do
       if (f[maxi,i]>0) and (f[maxj,i]>0) then mark(i,maxi,maxj);
   until (max1<0) or t;
   if t then write(0) else write(abs(max1));
end.
用并查集写的代码
在RQNOJ上测评0分    原因是无结果输出
但是在本机上已经过了样例数据了
为什么....


好吧...看了会动漫灵感一现...
判冲突有问题

program prison;
var f:array[1..20000,1..20000] of longint;
     n,m,i,j,k,max,max1,maxi,maxj:integer;
     t:boolean;
procedure recor(x,y:integer);
begin
   maxi:=x;
   maxj:=y;
   max1:=abs(f[x,y]);
end;
procedure mark(x,y,z:integer);
begin
   if f[y,x]<f[z,x] then f[y,x]:=-f[y,x] else f[z,x]:=-f[z,x];
end;
function min(w,x,y,z:integer):longint;
begin
   min:=f[w,y];
   if min<f[w,z] then min:=f[w,z];
   if min<f[x,y] then min:=f[x,y];
   if min<f[x,z] then min:=f[x,z];
end;
begin
   readln(n,m);
   for i:=1 to m do
     begin
       read(j,k);
       readln(f[j,k]);
     end;
   repeat
     max1:=0;
     t:=true;
     for i:=1 to n do
       for j:=i+1 to n do
         begin
           if max1<abs(f[i,j]) then recor(i,j);
           if f[i,j]>0 then t:=false;
         end;
     if f[maxi,maxj]<0 then max1:=f[maxi,maxj] else f[maxi,maxj]:=0;
     for i:=maxj+1 to n do
       begin
         if (f[maxi,i]>0) and (f[maxj,i]>0) then mark(i,maxi,maxj);
         for j:=i+1 to n do
           if (f[i,j]>0) and (f[i,j]<min(maxi,maxj,i,j)) then f[i,j]:=-f[i,j];
       end;
     for i:=1 to maxi-1 do
       for j:=1 to i+1 do
         if (f[i,j]>0) and (f[i,j]<min(i,j,maxi,maxj)) then f[i,j]:=-f[i,j];
   until (max1<0) or t;
   if t then write(0) else write(abs(max1));
end.
修改后的...还是不能AC
貌似还有没考虑到的冲突情况
求神牛现身指点下啊


program prison;
var f:array[1..20000,1..20000] of longint;
     n,m,i,j,k,max,max1,maxi,maxj:integer;
     t:boolean;
procedure recor(x,y:integer);
begin
   maxi:=x;
   maxj:=y;
   max1:=abs(f[x,y]);
end;
procedure mark(x,y,z:integer);
begin
   if f[y,x]<f[z,x] then f[y,x]:=-f[y,x] else f[z,x]:=-f[z,x];
end;
procedure mark1(x,y,z:integer);
begin
   if f[x,y]<f[x,z] then f[x,y]:=-f[x,y] else f[x,z]:=-f[x,z];
end;
function min(w,x,y,z:integer):longint;
begin
   min:=f[w,y];
   if min<f[w,z] then min:=f[w,z];
   if min<f[x,y] then min:=f[x,y];
   if min<f[x,z] then min:=f[x,z];
end;
function min1(w,x,y,z:integer):longint;
begin
   min1:=f[w,x];
   if min1<f[w,y] then min1:=f[w,y];
   if min1<f[x,z] then min1:=f[x,z];
   if min1<f[y,x] then min1:=f[y,z];
end;
begin
   readln(n,m);
   for i:=1 to m do
     begin
       read(j,k);
       readln(f[j,k]);
     end;
   repeat
     max1:=0;
     t:=true;
     for i:=1 to n do
       for j:=i+1 to n do
         begin
           if max1<abs(f[i,j]) then recor(i,j);
           if f[i,j]>0 then t:=false;
         end;
     if f[maxi,maxj]<0 then max1:=f[maxi,maxj] else f[maxi,maxj]:=0;
     for i:=maxj+1 to n do
       begin
         if (f[maxi,i]>0) and (f[maxj,i]>0) then mark(i,maxi,maxj);
         for j:=i+1 to n do
           if (f[i,j]>0) and (f[i,j]<min(maxi,maxj,i,j)) then f[i,j]:=-f[i,j];
       end;
     for i:=1 to maxi-1 do
       begin
         if (f[i,maxi]>0) and (f[i,maxj]>0) then mark1(i,maxi,maxj);
         for j:=1 to i+1 do
           if (f[i,j]>0) and (f[i,j]<min(i,j,maxi,maxj)) then f[i,j]:=-f[i,j];
       end;
     for i:=maxi+1 to maxj-1 do
      for j:=maxi+1 to maxj-1 do
        if (f[i,j]>0) and (f[i,j]<min(maxi,i,j,maxj)) then f[i,j]:=-f[i,j];
   until (max1<0) or t;
   if t then write(0) else write(abs(max1));
end.
可算AC了- -

现在想想考试的时候真够脑残的.竟然去开100k的数组.还好几个..不爆才怪
不过遍历20000*20000的二维是不是容易超时呀...