Program maxflow；
Type arr=Array[1..1000,1..1000]Of longint；
brr=Array[1..1000]Of longint；
Var c,f:Array[1..1000,1..1000]Of longint；
e,h:Array[1..1000]Of longint；
n,s,t:longint；
Function min(a,b:longint):longint；
Begin If a>b Then Exit(b)ELse Exit(a)；End；
Procedure push(a,b:longint)；
Var i:longint；
Begin
i:=min(e[a],c[a,b]-f[a,b])；
f[a,b]:=f[a,b]+i；
f[b,a]:=-f[a,b]；
e[a]:=e[a]-i；
e[b]:=e[b]+i；
End；
Procedure RELABEL(a:longint)；
Var i,min:longint；
Begin
min:=n；
For i:=1 to n do If c[a,i]-f[a,i]>0 Then
If h[i]<min Then min:=h[i]；
h[a]:=min+1；
End；
Procedure DISCHARGE(u:longint)；
Var i,j,cur,v:longint；
L:Array[1..1001]Of longint；
Begin
Fillchar(L,sizeof(L),0)；
j:=0；
For i:=1 to n do If((c[u,i]<>0)Or(c[i,u]<>0))And(c[u,i]-f[u,i]>0)Then Begin inc(j)；L[j]:=i；End；
cur:=1；
While e[u]>0 do Begin
v:=L[cur]；
If v=0 Then
Begin
RELABEL(u)；
cur:=1；
End
Else If(c[u,v]-f[u,v]>0)And(h[u]=h[v]+1)Then PUSH(u,v)
Else inc(cur)；
End；
End；
Procedure init；
Var i,m,x,y,z:longint；
Begin
Readln(m,n)；
For i:=1 to m do Begin
Readln(x,y,z)；
c[x,y]:=z；
End；
s:=1；t:=n；
Fillchar(h,sizeof(h),0)；
Fillchar(e,sizeof(e),0)；
Fillchar(f,sizeof(f),0)；
h[s]:=n；
For i:=1 to n do If c[s,i]<>0 Then Begin
f[s,i]:=c[s,i]；
f[i,s]:=-c[s,i]；
e[i]:=c[s,i]；
e[s]:=e[s]-c[s,i]；
End；
End；
Procedure R_F；
Var i,j,k,a:longint；
l:Array[1..1001]Of longint；
Begin
init；
Fillchar(l,sizeof(l),0)；
j:=0；
For i:=1 to n do If Not(i in[s,t])Then Begin inc(j)；l[j]:=i；End；
i:=l[1]；j:=1；
While i<>0 do Begin
a:=h[i]；
DISCHARGE(i)；
If h[i]>a Then Begin
For k:=j-1 downto 1 do l[k+1]:=l[k]；
l[1]:=i；j:=1；
End；
inc(j)；i:=l[j]；
End；
Writeln(e[t])；
End；
Begin
R_F；
End.
状态题目:学生运输
状态编号: [查看该题]
状态: Unaccepted
测评机： Xeost[5]
得分： 60分
提交日期： 2008-6-26 15:11:00
有效耗时： 该状态没有记录
测试结果1: 测试结果正确
测试结果2: 测试结果正确
测试结果3: 测试结果正确
测试结果4: 测试结果正确
测试结果5: 无输出|运行超时
测试结果6: 无输出|运行超时
测试结果7: 测试结果正确
测试结果8: 无输出|运行超时
测试结果9: 无输出|运行超时
测试结果10: 测试结果正确