网络流小结

网络流主要包括：

1、最大流

2、费用流

3、有上下界的网络流

网络流的基本技巧：

1、多个源点和汇点的情况。建立超级源点和超级汇点。

2、顶点有容量限制。拆成两个点，此两点连边，容量为原来的点被限制的容量。

3、最大费用转为最小费用。变负数，最后变回来。

一、最大流

最大流算法的思想是不断地找S到T的增广路。算法的效率是由找增广路的方法决定的。

Edmond - Karp算法：用广搜找增广路，时间复杂度 O (n*m*m )。思路最简单。

 1 const int N=110, INF=0x3f3f3f3f;
 2 int Map[N][N],pre[N],n,ans;
 3 bool vis[N];
 4 queue<int> que;
 5 bool EK_bfs(int s,int e)
 6 {
 7     int i,k;
 8     while(!que.empty()) que.pop();
 9     memset(vis,0,sizeof(vis));
10     memset(pre,0,sizeof(pre));
11     que.push(s);
12     vis[s]=1;
13     while(!que.empty())
14     {
15         k=que.front();
16         if(e==k)  return 1;
17         que.pop();
18         for(i=1;i<=n;i++)
19         {
20             if(Map[k][i]&&!vis[i])
21             {
22                 vis[i]=1;
23                 pre[i]=k;
24                 que.push(i);
25             }
26         }
27     }
28     return 0;
29 }
30 void EK(int s,int e)
31 {
32     int u,mn;
33     ans=0;
34     while(EK_bfs(s,e))
35     {
36         mn=INF;
37         u=e;
38         while(pre[u]!=-1)
39         {
40             mn=min(mn,Map[pre[u]][u]);
41             u=pre[u];
42         }
43         ans+=mn;
44         u=e;
45         while(pre[u]!=-1)
46         {
47             Map[pre[u]][u]-=mn;
48             Map[u][pre[u]]+=mn;
49             u=pre[u];
50         }
51     }
52 }
53 void init()
54 {
55     memset(Map,0,sizeof(Map));
56 }

View Code

SAP算法：在寻找增广路的时候用了允许弧，并且用了Dinic算法的优化。时间复杂度为O(m*n*n)。

 1 const int N=110;
 2 const int M=2*N*N, INF=0x3f3f3f3f;
 3 struct node
 4 {
 5     int to,next,w;
 6 }edge[M];
 7 int head[N],numh[N],h[N],cure[N],pre[N];
 8 //numh:GAP优化的统计高度数量数组; h：距离标号数组; cure:当前弧
 9 int ans,tot;
10 void SAP(int s, int e,int n)
11 {
12     int flow,u,tmp,neck,i;
13 ans=0;
14 memset(pre,-1,sizeof(pre));
15     memset(h,0,sizeof(h));
16     memset(numh,0,sizeof(numh));
17     for(i=1;i<=n;i++)
18         cure[i]=head[i];
19     numh[0]=n;
20     u=s;
21     while(h[s]<n)
22     {
23         if(u==e)
24         {
25             flow =INF;
26             for(i=s;i!=e;i=edge[cure[i]].to)
27             {
28                 if(flow>edge[cure[i]].w)
29                 {
30                     neck=i;
31                     flow =edge[cure[i]].w;
32                 }
33             }
34             for(i=s;i!=e;i=edge[cure[i]].to)
35             {
36                 tmp=cure[i];
37                 edge[tmp].w-=flow;
38                 edge[tmp^1].w+=flow;
39             }
40             ans+=flow;
41             u=neck;
42         }
43         for(i=cure[u];i!=-1;i=edge[i].next)
44             if(edge[i].w && h[u]==h[edge[i].to]+1) break;
45         if(i!=-1) {cure[u]=i;pre[edge[i].to]=u;u=edge[i].to;}
46         else
47         {
48             if(0==--numh[h[u]]) break; //GAP优化
49             cure[u]=head[u];
50             for(tmp=n,i=head[u];i!=-1;i=edge[i].next)
51                 if(edge[i].w) tmp=min(tmp, h[edge[i].to]);
52             h[u]=tmp+1;
53             ++numh[h[u]];
54             if(u!=s) u=pre[u];
55         }
56     }
57 }
58 void init()
59 {
60     tot=0;
61     memset(head,-1,sizeof(head));
62 }
63 void addedge(int i,int j,int w)
64 {
65     edge[tot].to=j;edge[tot].w=w;edge[tot].next=head[i];head[i]=tot++;
66     edge[tot].to=i;edge[tot].w=0;edge[tot].next=head[j];head[j]=tot++;
67 }

View Code

Dinic算法：时间复杂度为O(m*n*n)。

 1 const int N=110;
 2 const int M=2*N*N, INF=0x3f3f3f3f;
 3 struct node
 4 {
 5     int to,next,w;
 6 }edge[M];
 7 int level[N],que[N],head[N];
 8 int tot,ans;
 9 bool makelevel(int s, int t)
10 {
11     memset(level,0,sizeof(level));
12     level[s]=1;
13     int iq=0 , i, k, top;
14     que[iq++]=s;
15     for(i=0;i<iq;i++)
16     {
17         top=que[i];
18         if(top==t) return 1;
19         for(k=head[top];k!=-1;k=edge[k].next)
20             if(!level[edge[k].to] && edge[k].w)
21             {
22                 que[iq++]=edge[k].to;
23                 level[edge[k].to]=level[top]+1;
24             }
25     }
26     return 0;
27 }
28 int DFS(int now, int maxf, int t)
29 {
30     if(now ==t) return maxf;
31     int ret=0, f, k;
32     for(k=head[now];k!=-1;k=edge[k].next)
33     {
34         if(edge[k].w && level[edge[k].to]==level[now]+1)
35         {
36             f=DFS(edge[k].to, min(maxf-ret,edge[k].w), t);
37             edge[k].w-=f;
38             edge[k^1].w+=f;
39             ret+=f;
40             if(ret==maxf) return ret;
41         }
42     }
43     return ret;
44 }
45 void DINIC(int s, int t)
46 {
47     ans=0;
48     while(makelevel(s,t)) ans+=DFS(s,INF,t);
49 }
50 void init()
51 {
52     tot=0;
53     memset(head,-1,sizeof(head));
54 }
55 void addedge(int i,int j,int w)
56 {
57     edge[tot].to=j;edge[tot].w=w;edge[tot].next=head[i];head[i]=tot++;
58     edge[tot].to=i;edge[tot].w=0;edge[tot].next=head[j];head[j]=tot++;
59 }

View Code

个人体会：最大流的题目一般不要求对算法进行修改（模版），难点在于如何把问题转为最大流问题，建图是一个难点。巧妙的建图可以把点的数量减少，从而减少时间复杂度。有一个文档叫网络流建模汇总，做得非常好。

题目链接http://www.cnblogs.com/Potato-lover/category/611621.html

1、判断满流

3572 Task Schedule

2883 kebab

2、二分+最大流

传送门：

3、最短路+最大流

3416 Marriage Match IV

二、费用流

一般情况下都是求最大流条件下的最小费用。

算法：连续最短路算法。

时间复杂度O（C*k*m），C是最终的流量，k*m就是SPFA算法的时间复杂度。

 1 const int N =1010, M=50010,INF=0x3f3f3f3f;
 2 struct node
 3 {
 4     int to, next, c ,f;//c是容量，f是费用
 5 }edge[M];
 6 int head[N],dis[N],load[N],p[N];
 7 bool vis[N];
 8 int tot,flow,cost;
 9 bool spfa(int S, int E,int n)
10 {
11     int que[N*10],qout,qin;
12     memset(vis,0,sizeof(vis));
13     memset(load,-1,sizeof(load));
14     memset(p,-1,sizeof(p));
15     for(int i=0;i<=n;i++)
16         dis[i]=INF;
17     qin=qout=0;
18     que[qin++]=S;
19     dis[S]=0;
20     vis[S]=1;
21     while(qin!=qout)
22     {
23         int u=que[qout++];
24         vis[u]=0;
25         for(int i=head[u];i!=-1;i=edge[i].next)
26         {
27             if(edge[i].c)
28             {
29                 int v=edge[i].to;
30                 if(dis[v]-dis[u]>edge[i].f)
31                 {
32                     dis[v]=dis[u]+edge[i].f;
33                     p[v]=u;
34                     load[v]=i;
35                     if(!vis[v])
36                     {
37                         vis[v]=1;
38                         que[qin++]=v;
39                     }
40                 }
41             }
42         }
43     }
44     if(dis[E]==INF) return 0;
45     return 1;
46 }
47 void MCF(int S, int E,int n)
48 {
49     int u,mn;
50     flow=cost=0;
51     while(spfa(S,E,n))
52     {
53         u=E; mn=INF;
54         while(p[u]!=-1)
55         {
56             mn=min(edge[load[u]].c, mn);
57             u=p[u];
58         }
59         u=E;
60         while(p[u]!=-1)
61         {
62             edge[load[u]].c-=mn;
63             edge[load[u]^1].c+=mn;
64             u=p[u];
65         }
66         cost+=dis[E]*mn;
67         flow+=mn;
68     }
69 }
70 void addedge(int a,int b,int c,int d)
71 {
72     edge[tot].to=b;edge[tot].c=c;edge[tot].f=d;
73     edge[tot].next=head[a];head[a]=tot++;
74     edge[tot].to=a;edge[tot].c=0;edge[tot].f=-d;
75     edge[tot].next=head[b];head[b]=tot++;
76 }
77 void init()
78 {
79     tot=0;
80     memset(head,-1,sizeof(head));
81 }

View Code

题目链接：http://www.cnblogs.com/Potato-lover/category/615756.html

三、有上下界的网络流

已经做过总结：http://www.cnblogs.com/Potato-lover/p/4002823.html