procedure addedge(u,v,cap:longint);
begin
sid[tot].u:=u;
sid[tot].v:=v;
sid[tot].cap:=cap;
sid[tot].next:=nd[u];
nd[u]:=tot;
inc(tot);
sid[tot].u:=v;
sid[tot].v:=u;
sid[tot].cap:=0;
sid[tot].next:=nd[v];
nd[v]:=tot;
inc(tot);
end;
function bfs:boolean;
var
i,head,tail,u,p:longint;
begin
for i:=0 to n*m+1 do
dep[i]:=-1;
dep[0]:=0;
head:=1;tail:=1;dl[1]:=0;
while head<=tail do
begin
u:=dl[head];
p:=nd[dl[head]];
while p<>-1 do
begin
if (sid[p].cap>0) and (dep[sid[p].v]=-1) then
begin
dep[sid[p].v]:=dep[u]+1;
if sid[p].v=n*m+1 then exit(true);
inc(tail);
dl[tail]:=sid[p].v;
end;
p:=sid[p].next;
end;
inc(head);
end;
exit(false);
end; function dinic:longint;
var
top,i,u,mi,last:longint;
begin
dinic:=0;
while bfs do
begin
fillchar(stack,sizeof(stack),0);
top:=0;
for i:=0 to n*m+1 do cur[i]:=nd[i];
u:=0;
while true do
begin
if u=n*m+1 then
begin mi:=maxlongint;
for i:=1 to top do
begin
if sid[stack[i]].cap<mi then
begin
last:=i;
mi:=sid[stack[i]].cap;
end;
end; for i:=1 to top do
begin
dec(sid[stack[i]].cap,mi);
inc(sid[stack[i] xor 1].cap,mi);
end; top:=last-1;
dinic:=dinic+mi;
u:=sid[stack[last]].u;
end; while cur[u]<>-1 do
begin
if (dep[sid[cur[u]].v]=dep[u]+1) and (sid[cur[u]].cap<>0) then break
else cur[u]:=sid[cur[u]].next;
end; if cur[u]=-1 then
begin
if u=0 then break;
dep[u]:=-1;
u:=sid[stack[top]].u;
dec(top);
end else
begin
inc(top);
stack[top]:=cur[u];
u:=sid[cur[u]].v;
end;
end;
end;
end;
最大流=最小割=正点权和-最大闭合权图
其中求最大闭合权图时，源点向所有点权为正的点连容量为点权的边，所有点权为负的点向汇点连容量为点权绝对值的边
表示约束关系的边容量为无穷大,i前必须做j，i连向j
-----------------------------------------------------------------------------------------------
void addedge2(int u,int v,int cap){
sid[cnt].next=nd[u];sid[cnt].des=v;sid[cnt].cap=cap;nd[u]=cnt;sid[cnt].fr=u;cnt++;
sid[cnt].next=nd[v];sid[cnt].des=u;sid[cnt].cap=;nd[v]=cnt;sid[cnt].fr=v;cnt++;
}
int bfs(){
memset(dep,-,sizeof(dep));
int head=,tail=;
dep[sor]=;dl[head]=sor;
while (head<=tail){
for (int p=nd[dl[head]];p!=-;p=sid[p].next)
if ((dep[sid[p].des]==-)&&(sid[p].cap)) dep[sid[p].des]=dep[dl[head]]+,dl[++tail]=sid[p].des;
head++;
}
if (dep[tar]==-) return();else return();
}
int dinic(){
int maxflow=;
while (bfs()){
for (int i=;i<=tar;i++) cur[i]=nd[i];
int u=sor,top=;
while(){
if (u==tar){
int mi=1e9,last;
for (int i=;i<=top;i++)
if (sid[sta[i]].cap<mi)
{mi=sid[sta[i]].cap;last=i;}
for (int i=;i<=top;i++)
sid[sta[i]].cap-=mi,sid[sta[i]^].cap+=mi;
u=sid[sta[last]].fr;cur[u]=sid[cur[u]].next;top=last-;
maxflow+=mi;
continue;
}
while((cur[u]!=-)&&((sid[cur[u]].cap==)||(dep[sid[cur[u]].des]!=dep[u]+)))
cur[u]=sid[cur[u]].next;
if (cur[u]!=-){sta[++top]=cur[u];u=sid[cur[u]].des;continue;}
else{
if (u==sor) break;
dep[u]=-;
u=sid[sta[top--]].fr;
continue;
}
}
}
return(maxflow);
}