非常感谢！

O(∩_∩)O哈哈~

同胞啊~~~

昨天才学的dinic……

AC了 vijos 上 两个通过人数比较多的题目……所以代码应该是对的吧……速度也都还不错……

刚好一个用的链表 还有一个用的邻接矩阵 。 DFS过程都是递归的，比较好理解。

第一题 最大权闭合子图 ， 建图写的好丑……

第二题 很简单 求最小割， 代码也比较简单

q：广搜用的队列

pre[x]：栈中x结点的前驱

gap[x]：x结点的标号

cur[x]：x结点的当前弧

me[x] ：用来记录源点--x结点的增广路上容量最小的边

program vj1352;

const

maxn=55000;

maxm=350000;

maxnum=50000000;

type

edge=record

v,c,next,f:longint;

end;

var

e:array[0..maxm]of edge;

st,ed,pre,gap,me,cur:array[0..maxn+1]of longint;

p:array[0..maxn+1]of boolean;

q:array[1..maxn+1]of longint;

tt,s,t,ans:longint;

procedure init;

var

i,j,x,y,n,m:longint;

begin

readln(n,m); t:=n+m+1; s:=0;

tt:=0;

for i:=1 to n do

begin

read(j); inc(tt); st[i]:=tt; ed[i]:=tt;

with e[tt] do

begin

v:=t; c:=j; next:=0

end

end;// for i

st:=tt+1; ed:=0;

for i:=1 to m do

begin

readln(x,y,j); inc(ans,j); inc(tt);

with e[tt] do

begin

v:=n+i; c:=j; next:=0

end;

e[ed].next:=tt; ed:=tt;

inc(tt); st[n+i]:=tt;

with e[tt] do

begin

v:=x; c:=maxnum; next:=tt+1

end;

inc(tt); ed[n+i]:=tt;

with e[tt] do

begin

v:=y; c:=maxnum; next:=0

end

end;// for i

//---|---|---|---|---|---|---|---|---|--

j:=tt;

for i:=0 to t do

begin

x:=st[i];

while x0 do

begin

if x>j then break;

inc(tt); e[x].f:=tt;

with e[tt] do

begin

v:=i; c:=0; f:=x; next:=0

end;

with e[x] do

begin

e[ed[v]].next:=tt; ed[v]:=tt;

x:=next

end

end// while

end// for i

end;// init

procedure dinic;

var

maxflow,i,j:longint;

function check:boolean;

var

x,hd,tl:longint;

begin

fillchar(p,sizeof(p),0);

fillchar(gap,sizeof(gap),0);

hd:=1; tl:=1;

q[1]:=s; gap:=0; p:=true;

while hd0)and(not p[v]) then

begin

gap[v]:=gap[q[hd]]+1;

if v=t then exit(true);

inc(tl); q[tl]:=v; p[v]:=true

end;

x:=next

end;// while x

inc(hd)

end;// BFS

exit(false)

end;// check

procedure dfs(x:longint);

begin

if x=t then

begin

j:=e[me[t]].c;

inc(maxflow,j);

i:=t;

while is do

begin

dec(e[pre[i]].c,j); inc(e[e[pre[i]].f].c,j);

i:=e[e[pre[i]].f].v

end;

exit

end;

while cur[x]0 do

with e[cur[x]] do

begin

if (c>0)and(gap[x]+1=gap[v]) then

begin

if c

加油吧

同情你，我学DINIC的时候也是找不到源代码，后来自己硬着头皮写出来的

代码高度模块化，这样有利于你理解，比赛时尽量压缩一下

本代码是POJ1273的代码，程序可能比较丑，凑合看吧

const maxn=200;

con=200000000;

type rec=record x,l,df:longint; end;

var g:array[1..maxn,1..maxn] of longint; //g表示边ij可增广流量

n,m,s,t,top,ans:longint;

dui,level:array[1..maxn] of longint; //dui表示队列

zh:array[1..maxn] of rec; //本人习惯：zh表示栈

function sma(x,y:longint):longint;

begin

if x0) and (level[r]+1=level[j]) then

begin

inc(top);

zh[top].l:=0; zh[top].x:=j;

zh[top].df:=sma(zh[top-1].df,g[r,j]);

end;

end;

procedure change; //找到完整增广路，开始修改； 顺便讲一下个人习惯：r边的起点，j是边的终点

var r,j,i,last,df:longint; //last记录修改后可到达的最远的一个点的栈编号

begin

j:=t; df:=zh[top].df; inc(ans,df);

for i:=top-1 downto 1 do

begin

r:=zh[i].x;

dec(g[r,j],df); dec(zh[i].df,df);

inc(g[j,r],df); //在反向弧加可增流量

if g[r,j]=0 then last:=i;

j:=r;

end;

top:=last;

end;

procedure bfs_level;

var f1,f2,i,r:longint;

begin

level:=1;

f1:=0; f2:=1; dui[1]:=s;

while f1f2 do

begin

inc(f1); r:=dui[f1];

if r=t then break;

for i:=2 to n do if (g[r,i]>0) and (level[i]=-10) then

begin

level[i]:=level[r]+1;

inc(f2); dui[f2]:=i;

end;

end;

end;

procedure dfs_maxflow; //这是非递归的dinic

var r,i:longint;

begin

repeat

for i:=1 to n do level[i]:=-10;

top:=1; zh[1].x:=s; zh[1].df:=con; zh[1].l:=0; //初始化,con代表正无穷

bfs_level;

while top>0 do

begin

r:=zh[top].x;

if r=t then change

else

begin

inc(zh[top].l);

if zh[top].l>n then begin level[r]:=-10; dec(top); end //退栈

else expand(r,zh[top].l);

end;

end;

until level[t]=-10;

end;

begin

while not eof do

begin

fillchar(g,sizeof(g),0);

ans:=0;

ready;

dfs_maxflow;

writeln(ans);

end;

end.