学到很多知识的一道题目
一开始读错题，后来发现是每条边必须至少访问一次
明显是一个有下界的最小流
首先是我自己脑补的比较渣的算法，可以无视：
对于有下界的最小流，我不会做，但是我会做有下界的费用流，而且注意这是一个DAG图
只要对每条边建x-->y （flow=1 cost=-inf）和x-->y (flow=inf cost=0)这样两条边
（这是解决DAG图的有下界费用流的非常简便的做法，通过附加边，根据最短路原理一定能保证这条边下界流量被流过）
然后从源点到每个出度非0的点连一条cost=1 flow=inf的边，出度为0的点到汇点连边flow=inf cost=0
然后跑最小费用流（注意这里并不是最大流，只要增广到正费用，就代表原图的边都被走过了，可以直接退出）
最后再加上m*inf即是ans
但是很可惜，这个方法虽然容易想，但是跑得慢（1100ms) 而最优的解法是8ms，差距啊……
本着精益求精的精神，下面介绍有下界的网络流
首先这是一个有源有汇的有下界最小流，要想解决这个问题，就先要解决无源无汇有下界的可行流（循环流）
无源无汇是什么意思呢，那就表示每个点的出流=入流
令每条边上界为a，下界为b，则这样
我们考虑将有下界转化为下界为0的网络流，这样原来每条边的上界变成a-b
但经过这样更改流量是不守恒的，因此，我们添加源汇为s,t
令d(u）=该点入下界流和-该点出下界流和
如果d(u)>0 则连边s-->u flow=d(u)
如果d(u)<0 则连边u-->t flow=-d(u)
不难发现，如果要流量满足下界，那必然s延伸出的附加边一定是满流，这是有附加边流量的意义决定的
因此我们只要做s到t的最大流，然后判断s延伸出的附加边是否满流
如果满流，则存在循环流，如果不存在，那就无解
有了这个基础，我们就不难解决有源有汇的有上下界最大流的问题
首先先转化为已知问题，添加t-->s下界为0，上界为inf的边
这样就转化为无源无汇有下界的可行流，先按上述方法添加超级源汇ss，tt
然后判断是否存在可行流，存在则记为f1
然后再跑s-->t的最大流（这里是改造后的图，即每条边下界为0，上界为a-b）记为f2，
UPD:注意，这里最大流不是f1+f2而是单独的f2，为什么呢？
其实我们在跑完可行流之后，有些边的反向弧存了可行流的流量，这些反向弧可以构成s-->t流量为可行流的路径
所以f2实际上是包含可行流的，具体画一个图就明白了
容易出问题的是有源有汇的有上下界最小流
一开始很容易误认为，添加t-->s下界为0，上界为inf的边，做出来的可行流不就是最小流吗？
实际上是不对的，具体见http://www.cnblogs.com/kane0526/archive/2013/04/05/3001108.html
（注意那张图1--tt之间的边方向似乎反了）
可以发现，当出现循环流的时候，可行流会增大。
因此正确的做法是先不添加t-->s，直接按无源无汇有下界可行流做
然后再添加t-->s，然后再做ss到tt的最大流，如果附加边满流即有解，解就是t-->s实际流过的流量
这应该怎么理解呢?其实第一次做最大流就是在消去循环会带来增加的流量
好再回到这道题目上来，由于这道题目一定有解，而且源点，汇点所连的边下界为0
我们可以稍稍变动一下算法，具体见程序
const inf=;
type node=record
next,point,flow,cost:longint;
end; var edge:array[..] of node;
q:array[..] of longint;
p,d,pre,cur:array[..] of longint;
v:array[..] of boolean;
s,i,len,n,t,j,x,m:longint; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure add(x,y,f,c:longint);
begin
inc(len);
edge[len].point:=y;
edge[len].flow:=f;
edge[len].cost:=c;
edge[len].next:=p[x];
p[x]:=len;
end; function spfa:boolean;
var y,i,f,r,x:longint;
begin
d[]:=;
for i:= to t do
d[i]:=inf;
f:=;
r:=;
q[]:=;
fillchar(v,sizeof(v),false);
v[]:=true;
while f<=r do
begin
x:=q[f];
v[x]:=false;
i:=p[x];
while i<>- do
begin
y:=edge[i].point;
if edge[i].flow> then
if d[y]>d[x]+edge[i].cost then
begin
d[y]:=d[x]+edge[i].cost;
pre[y]:=x;
cur[y]:=i;
if not v[y] then
begin
inc(r);
q[r]:=y;
v[y]:=true;
end;
end;
i:=edge[i].next;
end;
inc(f);
end;
if d[t]=inf then exit(false) else exit(true);
end; function mincost:longint;
var i,j:longint;
begin
mincost:=;
while spfa do
begin
if d[t]> then exit; //关键
i:=t;
while i<> do
begin
j:=cur[i];
dec(edge[j].flow);
inc(edge[j xor ].flow);
i:=pre[i];
end;
mincost:=mincost+d[t];
end;
end; begin
len:=-;
fillchar(p,sizeof(p),);
readln(n);
t:=n+;
for i:= to n do
begin
read(s);
m:=m+s;
for j:= to s do
begin
read(x);
add(i,x,,-inf);
add(x,i,,inf);
add(i,x,inf,);
add(x,i,,);
end;
if s= then
begin
add(i,t,inf,);
add(t,i,,);
end
else begin
add(,i,inf,);
add(i,,,-);
end;
end;
writeln(mincost+m*inf);
end.
脑补的做法
const inf=;
type node=record
next,point,flow:longint;
end; var edge:array[..] of node;
p,d,pre,cur,numh,h,c:array[..] of longint;
v:array[..] of boolean;
s,i,len,n,t,j,x,m:longint; function min(a,b:longint):longint;
begin
if a>b then exit(b) else exit(a);
end; procedure add(x,y,f:longint);
begin
inc(len);
edge[len].point:=y;
edge[len].flow:=f;
edge[len].next:=p[x];
p[x]:=len;
end; function sap:longint;
var i,q,tmp,u,j,neck:longint;
begin
neck:=inf;
for i:= to t do
cur[i]:=p[i];
numh[]:=t+;
u:=;
sap:=;
while h[]<t+ do
begin
d[u]:=neck;
i:=cur[u];
while i<>- do
begin
j:=edge[i].point;
if (edge[i].flow>) and (h[u]=h[j]+) then
begin
pre[j]:=u;
cur[u]:=i;
neck:=min(neck,edge[i].flow);
u:=j;
if u=t then
begin
sap:=sap+neck;
while u<> do
begin
u:=pre[u];
j:=cur[u];
dec(edge[j].flow,neck);
inc(edge[j xor ].flow,neck);
end;
neck:=inf;
end;
break;
end;
i:=edge[i].next;
end;
if i=- then
begin
dec(numh[h[u]]);
if numh[h[u]]= then exit;
tmp:=t;
q:=-;
i:=p[u];
while i<>- do
begin
j:=edge[i].point;
if edge[i].flow> then
if h[j]<tmp then
begin
tmp:=h[j];
q:=i;
end;
i:=edge[i].next;
end;
cur[u]:=q;
h[u]:=tmp+;
inc(numh[h[u]]);
if u<> then
begin
u:=pre[u];
neck:=d[u];
end;
end;
end;
end; begin
len:=-;
fillchar(p,sizeof(p),);
readln(n);
t:=n+;
for i:= to n do
begin
read(s);
for j:= to s do
begin
read(x);
add(i,x,inf);
add(x,i,);
inc(c[x]);
dec(c[i]);
end;
end;
for i:= to n do
if c[i]> then
begin
m:=m+c[i];
add(,i,c[i]);
add(i,,);
end
else if c[i]< then
begin
add(i,t,-c[i]);
add(t,i,);
end; writeln(m-sap); //一定有解的时候只用跑一次，想想看为什么
end.
标算