[BZOJ2502]清理雪道有上下界网络流（最小流）

2502: 清理雪道

Time Limit: 10 Sec Memory Limit: 128 MB

Description

滑雪场坐落在FJ省西北部的若干座山上。

从空中鸟瞰，滑雪场可以看作一个有向无环图，每条弧代表一个斜坡（即雪道），弧的方向代表斜坡下降的方向。

你的团队负责每周定时清理雪道。你们拥有一架直升飞机，每次飞行可以从总部带一个人降落到滑雪场的某个地点，然后再飞回总部。从降落的地点出发，这个人可以顺着斜坡向下滑行，并清理他所经过的雪道。

由于每次飞行的耗费是固定的，为了最小化耗费，你想知道如何用最少的飞行次数才能完成清理雪道的任务。

Input

输入文件的第一行包含一个整数n (2 <= n <= 100) – 代表滑雪场的地点的数量。接下来的n行，描述1~n号地点出发的斜坡，第i行的第一个数为m (0 <= m < n) ，后面共有m个整数，由空格隔开，每个整数a互不相同，代表从地点i下降到地点a的斜坡。每个地点至少有一个斜坡与之相连。

Output

输出文件的第一行是一个整数k – 直升飞机的最少飞行次数。

Sample Input

8
1 3
1 7
2 4 5
1 8
1 8
0
2 6 5
0

Sample Output

题解：

接触到的第一道上下界网络流题目……我怎么什么题都不会啊.jpg

如果你对上下界网络流没有接触的话，首先安利一波liu_runda学长的学习笔记，

讲的十分详细:http://www.cnblogs.com/liu-runda/p/6262832.html

在你已经会来上下界网络流之后……

大概这是一道水题吧233

先计算出附加流，然后从附加源ss跑到附加汇tt的最大流，

这样我们就得到了一个可行流，在t->s的弧上面把可行流的流量ans1提取出来。

然后我们去掉t->s的弧以及ss，tt两个附加点，再跑一边t->s最大流

由于反向边的流量增加意味着正向边的流量减少，所以设这样跑出来的最大流是ans2，答案就是ans1-ans2。

这样我们就解决了本题。代码实现：

 #include <cstdio>

 #include <cstring>

 #include <algorithm>

 using namespace std;

 const int N=,inf=0x7fffffff;

 struct edge{int zhong,next,flow;};

 struct NetWork

 {

     int n,S,T,e,adj[N],cur[N];

     int hd,tl,que[N],dist[N],gap[N];

     edge s[N<<];

     inline void intn(int sz)

     {

         n=sz,e=,memset(adj,,sizeof(adj));

         memset(dist,,sizeof(dist));

         memset(gap,,sizeof(gap));

     }

     inline void add(int qi,int zhong,int flow)

         {s[++e].zhong=zhong;s[e].next=adj[qi];adj[qi]=e;s[e].flow=flow;}

     inline void bfs()

     {

         hd=,tl=,dist[T]=,que[++tl]=T;

         register int i,x,u;

         while(hd<=tl)

             for(x=que[hd++],++gap[dist[x]],i=adj[x];i;i=s[i].next)

                 if(!dist[s[i].zhong])

                     dist[s[i].zhong]=dist[x]+,que[++tl]=s[i].zhong;

     }

     int Shoot(int rt,int maxf)

     {

         if(rt==T||!maxf)return maxf;

         register int i,f,ret=;

         for(i=cur[rt];i;i=s[i].next)

             if(s[i].flow&&dist[rt]==dist[s[i].zhong]+)

             {

                 f=Shoot(s[i].zhong,min(s[i].flow,maxf)),

                 maxf-=f,ret+=f,s[i].flow-=f,s[i^].flow+=f;

                 if(!maxf)return ret;

             }

         if(!(--gap[dist[rt]]))dist[S]=n+;

         ++gap[++dist[rt]],cur[rt]=adj[rt];

         return ret;

     }

     inline int ISAP(int a,int b)

     {

         S=a,T=b;int maxf=;bfs();

         memcpy(cur,adj,sizeof(adj));

         while(dist[S]<=n)maxf+=Shoot(S,inf);

         return maxf;

     }

     inline void cut_off(int x)

     {

         register int i;

         for(i=adj[x];i;i=s[i].next)

             s[i].flow=s[i^].flow=;

     }

     inline void get_ans(int a,int b,int ss,int tt)

     {

         add(b,a,inf),add(a,b,),ISAP(ss,tt);

         int ans=s[e].flow;

         s[e].flow=s[e^].flow=;

         cut_off(ss),cut_off(tt);

         printf("%d\n",ans-ISAP(b,a));

     }

 }SAP;

 int n,m,S,T,SS,TT;

 int rudu[N],chudu[N],du[N];

 int main()

 {

     scanf("%d",&n),S=,T=n+,SS=T+,TT=SS+;

     SAP.intn(TT+);

     register int a,b,i,j;

     for(i=;i<=n;++i)

         for(scanf("%d",&a),j=;j<=a;++j)

             scanf("%d",&b),++du[b],--du[i],

             ++chudu[i],++rudu[b],

             SAP.add(i,b,inf),SAP.add(b,i,);

     for(i=;i<=n;++i)

     {

         if(!rudu[i])SAP.add(S,i,inf),SAP.add(i,S,);

         if(!chudu[i])SAP.add(i,T,inf),SAP.add(T,i,);

     }

     for(i=;i<=n;++i)

     {

         if(du[i]>)SAP.add(SS,i,du[i]),SAP.add(i,SS,);

         if(du[i]<)SAP.add(i,TT,-du[i]),SAP.add(TT,i,);

     }

     SAP.get_ans(S,T,SS,TT);

 }

雪道