学到很多知识的一道题目
一开始读错题，后来发现是每条边必须至少访问一次
明显是一个有下界的最小流
首先是我自己脑补的比较渣的算法，可以无视：
对于有下界的最小流，我不会做，但是我会做有下界的费用流，而且注意这是一个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
我们可以稍稍变动一下算法，具体见程序
1 const inf=10000; 2 type node=record 3 next,point,flow,cost:longint; 4 end; 5 6 var edge:array[0..400010] of node; 7 q:array[0..400010] of longint; 8 p,d,pre,cur:array[0..200] of longint; 9 v:array[0..200] of boolean; 10 s,i,len,n,t,j,x,m:longint; 11 12 function min(a,b:longint):longint; 13 begin 14 if a>b then exit(b) else exit(a); 15 end; 16 17 procedure add(x,y,f,c:longint); 18 begin 19 inc(len); 20 edge[len].point:=y; 21 edge[len].flow:=f; 22 edge[len].cost:=c; 23 edge[len].next:=p[x]; 24 p[x]:=len; 25 end; 26 27 function spfa:boolean; 28 var y,i,f,r,x:longint; 29 begin 30 d[0]:=0; 31 for i:=1 to t do 32 d[i]:=inf; 33 f:=1; 34 r:=1; 35 q[1]:=0; 36 fillchar(v,sizeof(v),false); 37 v[0]:=true; 38 while f<=r do 39 begin 40 x:=q[f]; 41 v[x]:=false; 42 i:=p[x]; 43 while i<>-1 do 44 begin 45 y:=edge[i].point; 46 if edge[i].flow>0 then 47 if d[y]>d[x]+edge[i].cost then 48 begin 49 d[y]:=d[x]+edge[i].cost; 50 pre[y]:=x; 51 cur[y]:=i; 52 if not v[y] then 53 begin 54 inc(r); 55 q[r]:=y; 56 v[y]:=true; 57 end; 58 end; 59 i:=edge[i].next; 60 end; 61 inc(f); 62 end; 63 if d[t]=inf then exit(false) else exit(true); 64 end; 65 66 function mincost:longint; 67 var i,j:longint; 68 begin 69 mincost:=0; 70 while spfa do 71 begin 72 if d[t]>0 then exit; //关键 73 i:=t; 74 while i<>0 do 75 begin 76 j:=cur[i]; 77 dec(edge[j].flow); 78 inc(edge[j xor 1].flow); 79 i:=pre[i]; 80 end; 81 mincost:=mincost+d[t]; 82 end; 83 end; 84 85 begin 86 len:=-1; 87 fillchar(p,sizeof(p),255); 88 readln(n); 89 t:=n+1; 90 for i:=1 to n do 91 begin 92 read(s); 93 m:=m+s; 94 for j:=1 to s do 95 begin 96 read(x); 97 add(i,x,1,-inf); 98 add(x,i,0,inf); 99 add(i,x,inf,0); 100 add(x,i,0,0); 101 end; 102 if s=0 then 103 begin 104 add(i,t,inf,0); 105 add(t,i,0,0); 106 end 107 else begin 108 add(0,i,inf,1); 109 add(i,0,0,-1); 110 end; 111 end; 112 writeln(mincost+m*inf); 113 end.
1 const inf=100007; 2 type node=record 3 next,point,flow:longint; 4 end; 5 6 var edge:array[0..400010] of node; 7 p,d,pre,cur,numh,h,c:array[0..200] of longint; 8 v:array[0..200] of boolean; 9 s,i,len,n,t,j,x,m:longint; 10 11 function min(a,b:longint):longint; 12 begin 13 if a>b then exit(b) else exit(a); 14 end; 15 16 procedure add(x,y,f:longint); 17 begin 18 inc(len); 19 edge[len].point:=y; 20 edge[len].flow:=f; 21 edge[len].next:=p[x]; 22 p[x]:=len; 23 end; 24 25 function sap:longint; 26 var i,q,tmp,u,j,neck:longint; 27 begin 28 neck:=inf; 29 for i:=0 to t do 30 cur[i]:=p[i]; 31 numh[0]:=t+1; 32 u:=0; 33 sap:=0; 34 while h[0]<t+1 do 35 begin 36 d[u]:=neck; 37 i:=cur[u]; 38 while i<>-1 do 39 begin 40 j:=edge[i].point; 41 if (edge[i].flow>0) and (h[u]=h[j]+1) then 42 begin 43 pre[j]:=u; 44 cur[u]:=i; 45 neck:=min(neck,edge[i].flow); 46 u:=j; 47 if u=t then 48 begin 49 sap:=sap+neck; 50 while u<>0 do 51 begin 52 u:=pre[u]; 53 j:=cur[u]; 54 dec(edge[j].flow,neck); 55 inc(edge[j xor 1].flow,neck); 56 end; 57 neck:=inf; 58 end; 59 break; 60 end; 61 i:=edge[i].next; 62 end; 63 if i=-1 then 64 begin 65 dec(numh[h[u]]); 66 if numh[h[u]]=0 then exit; 67 tmp:=t; 68 q:=-1; 69 i:=p[u]; 70 while i<>-1 do 71 begin 72 j:=edge[i].point; 73 if edge[i].flow>0 then 74 if h[j]<tmp then 75 begin 76 tmp:=h[j]; 77 q:=i; 78 end; 79 i:=edge[i].next; 80 end; 81 cur[u]:=q; 82 h[u]:=tmp+1; 83 inc(numh[h[u]]); 84 if u<>0 then 85 begin 86 u:=pre[u]; 87 neck:=d[u]; 88 end; 89 end; 90 end; 91 end; 92 93 begin 94 len:=-1; 95 fillchar(p,sizeof(p),255); 96 readln(n); 97 t:=n+1; 98 for i:=1 to n do 99 begin 100 read(s); 101 for j:=1 to s do 102 begin 103 read(x); 104 add(i,x,inf); 105 add(x,i,0); 106 inc(c[x]); 107 dec(c[i]); 108 end; 109 end; 110 for i:=1 to n do 111 if c[i]>0 then 112 begin 113 m:=m+c[i]; 114 add(0,i,c[i]); 115 add(i,0,0); 116 end 117 else if c[i]<0 then 118 begin 119 add(i,t,-c[i]); 120 add(t,i,0); 121 end; 122 123 writeln(m-sap); //一定有解的时候只用跑一次，想想看为什么 124 end.