网络流模板们

最大流EK：

 1 #include <vector>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #define N1 210
 6 #define M1 1010
 7 #define ll long long
 8 #define dd double
 9 #define inf 0x3f3f3f3f
10 using namespace std;
11 
12 int gint()
13 {
14     int ret=0,fh=1;char c=getchar();
15     while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();}
16     while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();}
17     return ret*fh;
18 }
19 
20 struct Edge{
21 int head[N1],to[M1<<1],nxt[M1<<1],val[M1<<1],cte;
22 void ae(int u,int v,int w)
23 {
24     cte++; to[cte]=v; val[cte]=w;
25     nxt[cte]=head[u]; head[u]=cte;
26 }
27 }e;
28 
29 int que[N1],hd,tl;
30 int flow[N1],id[N1];
31 
32 int bfs(int S,int T)
33 {
34     int x,j,v;
35     memset(flow,0,sizeof(flow));
36     memset(id,0,sizeof(id));
37     hd=1,tl=0; que[++tl]=S; flow[S]=inf;
38     while(hd<=tl)
39     {
40         x=que[hd++];
41         for(j=e.head[x];j;j=e.nxt[j])
42         {
43             v=e.to[j]; 
44             if(id[v]||e.val[j]==0) continue;
45             flow[v]=min(flow[x],e.val[j]);
46             id[v]=j; que[++tl]=v;
47         }
48     }
49     if(!flow[T]) return -1;
50     else return flow[T];
51 }
52 
53 int EK(int S,int T)
54 {
55     int x,mxflow=0,tmp;
56     while(1)
57     {
58         tmp=bfs(S,T); 
59         if(tmp==-1) return mxflow;
60         for(x=T;x!=S;x=e.to[id[x]^1])
61         {
62             e.val[id[x]]-=tmp;
63             e.val[id[x]^1]+=tmp;
64         }
65         mxflow+=tmp;
66     }
67 }
68 
69 int n,m,S,T;
70 
71 int main()
72 {
73     scanf("%d%d%d%d",&n,&m,&S,&T);
74     int i,j,k,x,y,z; e.cte=1;
75     for(i=1;i<=m;i++){ x=gint(); y=gint(); z=gint(); e.ae(x,y,z); e.ae(y,x,0); }
76     printf("%d
",EK(S,T));
77     return 0;
78 }

View Code

最大流Dinic：

 1 #include <vector>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #define N1 10010
 6 #define M1 100010
 7 #define ll long long
 8 #define dd double
 9 #define inf 0x3f3f3f3f
10 using namespace std;
11 
12 int gint()
13 {
14     int ret=0,fh=1;char c=getchar();
15     while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();}
16     while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();}
17     return ret*fh;
18 }
19 
20 struct Edge{
21 int head[N1],to[M1<<1],nxt[M1<<1],val[M1<<1],cte;
22 void ae(int u,int v,int w)
23 {
24     cte++; to[cte]=v; val[cte]=w;
25     nxt[cte]=head[u]; head[u]=cte;
26 }
27 }e;
28 
29 int que[N1],hd,tl,dep[N1],now[N1];
30 int n,m,S,T,mxflow; 
31 
32 int bfs()
33 {
34     int x,j,v;
35     memset(dep,-1,sizeof(dep));
36     memcpy(now,e.head,sizeof(e.head));
37     hd=1,tl=0; que[++tl]=S; dep[S]=0;
38     while(hd<=tl)
39     {
40         x=que[hd++];
41         for(j=e.head[x];j;j=e.nxt[j])
42         {
43             v=e.to[j];
44             if(dep[v]!=-1||!e.val[j]) continue;
45             dep[v]=dep[x]+1; que[++tl]=v;
46         }
47     }
48     if(dep[T]==-1) return 0;
49     else return 1;
50 }
51 
52 int dfs(int u,int limit)
53 {
54     if(!limit||u==T) return limit;
55     int j,v,flow,ans=0;
56     for(j=now[u];j;j=e.nxt[j])
57     {
58         now[u]=j; v=e.to[j]; 
59         if(dep[v]==dep[u]+1 && (flow=dfs(v,min(limit,e.val[j]))) )
60         {
61             limit-=flow; ans+=flow;
62             e.val[j]-=flow; e.val[j^1]+=flow;
63             if(!limit) break;
64         }
65     }
66     return ans;
67 }
68 
69 int Dinic()
70 {
71     while(bfs())
72     {
73         mxflow+=dfs(S,inf);
74     }
75     return mxflow;
76 }
77 
78 
79 int main()
80 {
81     scanf("%d%d%d%d",&n,&m,&S,&T);
82     int i,x,y,z,ans=0; e.cte=1;
83     for(i=1;i<=m;i++){ x=gint(); y=gint(); z=gint(); e.ae(x,y,z); e.ae(y,x,0); }
84     ans=Dinic();
85     printf("%d
",ans);
86     return 0;
87 }

View Code

费用流spfaEK：

 1 #include <vector>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #define N1 5010
 6 #define M1 50010
 7 #define ll long long
 8 #define dd double
 9 #define inf 0x3f3f3f3f
10 using namespace std;
11 
12 int gint()
13 {
14     int ret=0,fh=1;char c=getchar();
15     while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();}
16     while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();}
17     return ret*fh;
18 }
19 
20 int n,m,S,T;
21 struct Edge{
22 int head[N1],to[M1<<1],nxt[M1<<1],val[M1<<1],flow[M1<<1],cte;
23 void ae(int u,int v,int F,int W)
24 {
25     cte++; to[cte]=v; flow[cte]=F; val[cte]=W; 
26     nxt[cte]=head[u]; head[u]=cte;
27 }
28 }e;
29 
30 int que[M1<<1],dis[N1],flow[N1],use[N1],id[N1],hd,tl;
31 
32 int spfa()
33 {
34     int x,j,v;
35     memset(dis,0x3f,sizeof(dis)); memset(flow,0,sizeof(flow)); memset(use,0,sizeof(use));
36     hd=1,tl=0; que[++tl]=S; dis[S]=0; use[S]=1; flow[S]=inf;
37     while(hd<=tl)
38     {
39         x=que[hd++];
40         for(j=e.head[x];j;j=e.nxt[j])
41         {
42             v=e.to[j];
43             if(e.flow[j]>0&&dis[v]>dis[x]+e.val[j])
44             {
45                 dis[v]=dis[x]+e.val[j]; id[v]=j;
46                 flow[v]=min(flow[x],e.flow[j]);
47                 if(!use[v]) que[++tl]=v,use[v]=1;
48             }
49         }
50         use[x]=0;
51     }
52     return dis[T]!=inf;
53 }
54 
55 int mxflow=0,tot_cost=0;
56 void EK()
57 {
58     int x; mxflow=0,tot_cost=0;
59     while(spfa())
60     {
61         mxflow+=flow[T]; tot_cost+=dis[T]*flow[T];
62         for(x=T;x!=S;x=e.to[id[x]^1])
63         {
64             e.flow[id[x]]-=flow[T];
65             e.flow[id[x]^1]+=flow[T];
66         }
67     }
68 }
69 
70 
71 int main()
72 {
73     scanf("%d%d%d%d",&n,&m,&S,&T);
74     int i,a,b,c,d; e.cte=1;
75     for(i=1;i<=m;i++)
76     {
77         scanf("%d%d%d%d",&a,&b,&c,&d);
78         e.ae(a,b,c,d); e.ae(b,a,0,-d);
79     }
80     EK();
81     printf("%d %d
",mxflow,tot_cost);
82     return 0;
83 }

View Code

无源汇上下界可行流：

给定一张图，每条边都有对应的流量限制$[l,r]$，要求每条边的流量都在规定范围内

我们想办法去掉流量下界的限制，每条边流量上限改成$r-l$，然后跑最大流就行了

直接去掉是不行的

假设每条边都流了流量下界l点流量，此时一些点可能并不满足流量守恒

而我们最终建出来的网络流图中，每个点的出入流量显然是守恒的(除了源汇)

所以我们把点向源点汇点连边来让它流量守恒

具体做法是，手动建出源$S$汇$T$

点$x$的最小入流量$>$最小出流量，$S$向$x$连流量为差值的边，反之$x$向$T$连流量为差值的边

模拟出原图中流量下界对点的影响

然后跑最大流，每条边的实际流量=最小割后的流量+流量下界

如果在最小割图中源汇连出去的边没流满，说明有边的流量下界没达到，一定无解

  1 #include <cmath>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #define N1 210
  6 #define M1 40010
  7 #define ll long long
  8 using namespace std;
  9 const int inf=0x3f3f3f3f;
 10 
 11 int gint()
 12 {
 13     int ret=0,fh=1; char c=getchar();
 14     while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();}
 15     while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();}
 16     return ret*fh;
 17 }
 18 struct Edge{
 19 int to[M1<<1],nxt[M1<<1],flow[M1<<1],val[M1<<1],head[N1],cte;
 20 void ae(int u,int v,int f,int w)
 21 {
 22     cte++; to[cte]=v; nxt[cte]=head[u];
 23     head[u]=cte; flow[cte]=f; val[cte]=w;
 24 }
 25 }e;
 26 
 27 int n,m,S,T,hd,tl;
 28 int dep[N1],cur[N1],que[M1];
 29 
 30 int bfs()
 31 {
 32     int x,j,v;
 33     memset(dep,-1,sizeof(dep)); memcpy(cur,e.head,sizeof(cur));
 34     hd=1,tl=0; que[++tl]=S; dep[S]=0;
 35     while(hd<=tl)
 36     {
 37         x=que[hd++];
 38         for(j=e.head[x];j;j=e.nxt[j])
 39         {
 40             v=e.to[j]; 
 41             if( e.flow[j]>0 && dep[v]==-1 )
 42             {
 43                 dep[v]=dep[x]+1;
 44                 que[++tl]=v;
 45             }
 46         }
 47     }
 48     return dep[T]!=-1;
 49 }
 50 int dfs(int x,int limit)
 51 {
 52     if( (x==T) || (!limit) ) return limit;
 53     int j,v,flow,ans=0;
 54     for(j=cur[x];j;j=e.nxt[j])
 55     {
 56         cur[x]=j; v=e.to[j];
 57         if( (dep[v]==dep[x]+1) && ( flow=dfs(v,min(limit,e.flow[j])) ) )
 58         {
 59             e.flow[j]-=flow; limit-=flow;
 60             e.flow[j^1]+=flow; ans+=flow;
 61             if(!limit) break;
 62         }
 63     }
 64     return ans;
 65 }
 66 int Dinic()
 67 {
 68     int mxflow=0;
 69     while( bfs() )
 70     {
 71         mxflow+=dfs(S,inf);
 72     }
 73     return mxflow;
 74 }
 75 int ouc[N1],id[M1],Flow[M1];
 76 
 77 int main()
 78 {
 79     int i,j,x,y,v,l,r,ans; 
 80     scanf("%d%d",&n,&m); 
 81     S=0,T=n+1; e.cte=1;
 82     for(i=1;i<=m;i++) 
 83     {
 84         x=gint(), y=gint(), l=gint(), r=gint();
 85         e.ae(x,y,r-l,l); id[e.cte]=i; e.ae(y,x,0,l); 
 86         ouc[x]+=l; ouc[y]-=l; 
 87     }
 88     for(x=1;x<=n;x++) 
 89         if(ouc[x]<0) e.ae(S,x,-ouc[x],0), e.ae(x,S,0,0);
 90         else e.ae(x,T,ouc[x],0), e.ae(T,x,0,0);
 91     ans=Dinic();
 92     for(j=e.head[S];j;j=e.nxt[j])
 93     {
 94         v=e.to[j];
 95         if(e.flow[j]>0){ puts("NO"); return 0; }
 96     }
 97     for(j=e.head[T];j;j=e.nxt[j])
 98     {
 99         v=e.to[j]; 
100         if(e.flow[j^1]>0){ puts("NO"); return 0; }
101     }
102     puts("YES");
103     for(x=1;x<=n;x++)
104     for(j=e.head[x];j;j=e.nxt[j])
105     {
106         v=e.to[j];
107         if(!(j&1)) Flow[id[j]]=e.flow[j^1]+e.val[j];
108     }
109     for(i=1;i<=m;i++)
110         printf("%d
",Flow[i]);
111     return 0;
112 }

View Code

有源汇上下界最大流：

给定一张有源汇网络流图，每条边都有对应的流量限制$[l,r]$，要求每条边的流量都在规定范围内，求最大流

设$s$是原图源点，$t$是原图汇点，$S$是新建源点，$T$是新建汇点

先判断是否有可行流

已经给定了源汇，咋办？

因为$s$流出流量=$t$流入流量

所以$t$向$s$连一条流量为$inf$的边，就变成了无源汇上下界可行流问题

在残量网络中，可行流的部分已经被去掉了

那么$s$到$t$还可能有流量流过，以$s,t$为源点在残量网络中跑最大流即可

  1 #include <cmath>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #define N1 210
  6 #define M1 40010
  7 #define ll long long
  8 using namespace std;
  9 const int inf=0x3f3f3f3f;
 10 
 11 int gint()
 12 {
 13     int ret=0,fh=1; char c=getchar();
 14     while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();}
 15     while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();}
 16     return ret*fh;
 17 }
 18 struct Edge{
 19 int to[M1<<1],nxt[M1<<1],flow[M1<<1],head[N1],cte;
 20 void ae(int u,int v,int f)
 21 {
 22     cte++; to[cte]=v; nxt[cte]=head[u];
 23     head[u]=cte; flow[cte]=f; //val[cte]=w;
 24 }
 25 }e;
 26 
 27 int n,m,s,t,S,T,hd,tl;
 28 int dep[N1],cur[N1],que[M1];
 29 
 30 int bfs()
 31 {
 32     int x,j,v;
 33     memset(dep,-1,sizeof(dep)); memcpy(cur,e.head,sizeof(cur));
 34     hd=1,tl=0; que[++tl]=S; dep[S]=0;
 35     while(hd<=tl)
 36     {
 37         x=que[hd++];
 38         for(j=e.head[x];j;j=e.nxt[j])
 39         {
 40             v=e.to[j]; 
 41             if( e.flow[j]>0 && dep[v]==-1 )
 42             {
 43                 dep[v]=dep[x]+1;
 44                 que[++tl]=v;
 45             }
 46         }
 47     }
 48     return dep[T]!=-1;
 49 }
 50 int dfs(int x,int limit)
 51 {
 52     if( (x==T) || (!limit) ) return limit;
 53     int j,v,flow,ans=0;
 54     for(j=cur[x];j;j=e.nxt[j])
 55     {
 56         cur[x]=j; v=e.to[j];
 57         if( (dep[v]==dep[x]+1) && ( flow=dfs(v,min(limit,e.flow[j])) ) )
 58         {
 59             e.flow[j]-=flow; limit-=flow;
 60             e.flow[j^1]+=flow; ans+=flow;
 61             if(!limit) break;
 62         }
 63     }
 64     return ans;
 65 }
 66 int Dinic()
 67 {
 68     int mxflow=0;
 69     while( bfs() )
 70         mxflow+=dfs(S,inf);
 71     return mxflow;
 72 }
 73 int ouc[N1]; 
 74 
 75 int main()
 76 {
 77     int i,j,x,y,v,l,r,ans; 
 78     scanf("%d%d%d%d",&n,&m,&s,&t); 
 79     S=0,T=n+1; e.cte=1;
 80     for(i=1;i<=m;i++) 
 81     {
 82         x=gint(), y=gint(), l=gint(), r=gint();
 83         e.ae(x,y,r-l); e.ae(y,x,0); 
 84         ouc[x]+=l; ouc[y]-=l; 
 85     }
 86     for(x=1;x<=n;x++) 
 87         if(ouc[x]<0) e.ae(S,x,-ouc[x]), e.ae(x,S,0);
 88         else e.ae(x,T,ouc[x]), e.ae(T,x,0);
 89     e.ae(t,s,inf); e.ae(s,t,0);
 90     ans=Dinic(); S=0, T=n+1;
 91     for(j=e.head[S];j;j=e.nxt[j])
 92     {
 93         v=e.to[j];
 94         if(e.flow[j]>0){ puts("please go home to sleep"); return 0; }
 95     }
 96     for(j=e.head[T];j;j=e.nxt[j])
 97     {
 98         v=e.to[j]; 
 99         if(e.flow[j^1]>0){ puts("please go home to sleep"); return 0; }
100     }
101     S=s, T=t;
102     ans=Dinic();
103     printf("%d
",ans);
104     return 0;
105 }

View Code

有源汇上下界最小流：

给定一张有源汇网络流图，每条边都有对应的流量限制$[l,r]$，要求每条边的流量都在规定范围内，求最小流

建图和有源汇上下界最大流一样

在跑完可行流以后，先断开t->s这条边，再以t为源点，s为汇点跑最大流

答案是可行流后t->s这条边的流量+t到s的最大流

为什么是可行流t->s这条边的流量而不是最大流？

可行流仅仅是可行的，不一定是最小的

假设最小入流量$>$最小出流量的点称为入点，反之为出点

在跑可行流时，必需的可行流是这样流的：S->入点->t->s->出点->T

事实上，我们模拟的是这样一个过程：s->出点->入点->t

假如有一条流量是这样的：S->入点->出点->T

它模拟的是这样的过程：出点->入点

这种流量对于可行流而言是多余的，它应该在第二次从t->s这条流量里被冲掉

但由于它并不连接s,t导致它不会被干掉，所以这种情况并不能算到答案里

  1 #include <cmath>
  2 #include <cstdio>
  3 #include <cstring>
  4 #include <algorithm>
  5 #define N1 50010
  6 #define M1 200010
  7 #define ll long long
  8 using namespace std;
  9 const ll inf=0x3f3f3f3f3f3fll;
 10 
 11 int gint()
 12 {
 13     int ret=0,fh=1; char c=getchar();
 14     while(c<'0'||c>'9'){if(c=='-')fh=-1;c=getchar();}
 15     while(c>='0'&&c<='9'){ret=ret*10+c-'0';c=getchar();}
 16     return ret*fh;
 17 }
 18 struct Edge{
 19 int to[M1<<1],nxt[M1<<1],head[N1],cte; ll flow[M1<<1];
 20 void ae(int u,int v,ll f)
 21 {
 22     cte++; to[cte]=v; nxt[cte]=head[u];
 23     head[u]=cte; flow[cte]=f; //val[cte]=w;
 24 }
 25 }e;
 26 
 27 int n,m,s,t,S,T,hd,tl;
 28 int dep[N1],cur[N1],que[M1];
 29 
 30 int bfs()
 31 {
 32     int x,j,v;
 33     memset(dep,-1,sizeof(dep)); memcpy(cur,e.head,sizeof(cur));
 34     hd=1,tl=0; que[++tl]=S; dep[S]=0;
 35     while(hd<=tl)
 36     {
 37         x=que[hd++];
 38         for(j=e.head[x];j;j=e.nxt[j])
 39         {
 40             v=e.to[j]; 
 41             if( e.flow[j]>0 && dep[v]==-1 )
 42             {
 43                 dep[v]=dep[x]+1;
 44                 que[++tl]=v;
 45             }
 46         }
 47     }
 48     return dep[T]!=-1;
 49 }
 50 ll dfs(int x,ll limit)
 51 {
 52     if( (x==T) || (!limit) ) return limit;
 53     int j,v; ll flow,ans=0;
 54     for(j=cur[x];j;j=e.nxt[j])
 55     {
 56         cur[x]=j; v=e.to[j];
 57         if( (dep[v]==dep[x]+1) && ( flow=dfs(v,min(limit,e.flow[j])) ) )
 58         {
 59             e.flow[j]-=flow; limit-=flow;
 60             e.flow[j^1]+=flow; ans+=flow;
 61             if(!limit) break;
 62         }
 63     }
 64     return ans;
 65 }
 66 ll Dinic()
 67 {
 68     ll mxflow=0;
 69     while( bfs() )
 70         mxflow+=dfs(S,inf);
 71     return mxflow;
 72 }
 73 ll ouc[N1]; 
 74 
 75 int main()
 76 {
 77     int i,j,x,y,v,l,r; ll ans; 
 78     scanf("%d%d%d%d",&n,&m,&s,&t); 
 79     S=0,T=n+1; e.cte=1;
 80     for(i=1;i<=m;i++) 
 81     {
 82         x=gint(), y=gint(), l=gint(), r=gint();
 83         e.ae(x,y,r-l); e.ae(y,x,0); 
 84         ouc[x]+=l; ouc[y]-=l; 
 85     }
 86     for(x=1;x<=n;x++) 
 87         if(ouc[x]<0) e.ae(S,x,-ouc[x]), e.ae(x,S,0);
 88         else e.ae(x,T,ouc[x]), e.ae(T,x,0);
 89     e.ae(t,s,inf); e.ae(s,t,0);
 90     ans=Dinic(); S=0, T=n+1;
 91     for(j=e.head[S];j;j=e.nxt[j])
 92     {
 93         v=e.to[j];
 94         if(e.flow[j]>0){ puts("please go home to sleep"); return 0; }
 95     }
 96     for(j=e.head[T];j;j=e.nxt[j])
 97     {
 98         v=e.to[j]; 
 99         if(e.flow[j^1]>0){ puts("please go home to sleep"); return 0; }
100     }
101     for(j=e.head[t];j;j=e.nxt[j]) if(e.to[j]==s) 
102         ans=e.flow[j^1], e.flow[j]=0, e.flow[j^1]=0;
103     S=t, T=s;
104     ans-=Dinic();
105     printf("%lld
",ans);
106     return 0;
107 }

View Code