贪心还是差分约束?自己写的,但搞不清算法。。。无语

program Ltr;

const mxn=1001;mxm=10001;

var a,fr:array[1..mxn] of longint;

be,en:array[1..mxm] of longint;

ng,i,j,k,m,n,s,tp,t1,t2,t3,t4,t5:longint;

tf:boolean;

function back(x:longint):longint;

begin

if fr[x]=x then exit(x);

fr[x]:=back(fr[x]);

exit(fr[x]);

end;

begin

readln(n,m);ng:=0;

for i:=1 to n do fr[i]:=i;

for i:=1 to m do begin

read(t1,t2,t3);

if t3=0 then begin

t4:=back(t1);

t5:=back(t2);

if t4t5 then fr[t5]:=t4;

continue;

end;

if t3=1 then begin tp:=t1;t1:=t2;t2:=tp;end;

inc(ng);be[ng]:=t1;en[ng]:=t2;

end;

tf:=true;

for j:=1 to n do begin

if not tf then break;

tf:=false;

for i:=1 to ng do begin

t1:=back(be[i]);t2:=back(en[i]);

if a[t1]>=a[t2] then begin a[t2]:=a[t1]+1;tf:=true;end;

end;

end;

if tf then writeln('NO') else begin

tp:=0;

for i:=1 to n do if a[i]>tp then tp:=a[i];

writeln(tp);

end;

end.

2 条评论

  • 1

信息

ID
1094
难度
7
分类
图结构 | 差分约束 点击显示
标签
(无)
递交数
1964
已通过
396
通过率
20%
被复制
8
上传者