学到很多知识的一道题目

一开始读错题，后来发现是每条边必须至少访问一次

明显是一个有下界的最小流

首先是我自己脑补的比较渣的算法，可以无视：

对于有下界的最小流，我不会做，但是我会做有下界的费用流，而且注意这是一个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 then103     begin104       add(i,t,inf,0);105       add(t,i,0,0);106     end107     else begin108       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]
      
       -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]
       
        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   begin100     read(s);101     for j:=1 to s do102     begin103       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 do111     if c[i]>0 then112     begin113       m:=m+c[i];114       add(0,i,c[i]);115       add(i,0,0);116     end117     else if c[i]<0 then118     begin119       add(i,t,-c[i]);120       add(t,i,0);121     end;122 123   writeln(m-sap);  //一定有解的时候只用跑一次，想想看为什么124 end.