网络流建图总结

1.最小割

模型转化：原题求最小代价，则直接设割掉的是需要选择的。若原题求最大收益，则设割掉的是不选择的，最后用总和减去最小割就是答案。

1.1割的性质

• 性质1：(不连通)在给定的流网络中，去掉割的边集，则不存在任何一条从源到汇的路径。
• 性质2：(两类点)在给定的流网络中，任意一个割将点集划分成两部分。割为两部分点之前的“桥梁”。

1.2技巧

• 用正无限容量排除不参与决策的边。
• 使用割的定义式来分析最优性
• 利用源或汇关联的边容量处理点权
• 最小割和最大流是对偶问题，可以将问题的性质从边转化为点，从点转化为边

1.3最大闭合权图（选择了一些点必须要选择另一些点，偏序关系等）

1.3.1定义

• 闭合图定义：定义个一有向图\(G=(V,E)\)的闭合图是该有向图的一个点集，且该点集的所有出边都还指向该点集。即闭合图内的任意点的任意后继也一定在闭合图中。形式化定义就是：闭合图是这样的一个点集\(V^{'}\in V\)，满足对于\(\forall u\in V^{'}\)引出的\(\forall <u,v>\in E\)，必有\(v\in V^{'}\)成立。还有一种定义：满足对于\(\forall <u,v>\in E\)，若有\(u\in V^{'}\)，必有\(v\in V^{'}\)成立。
• 最大闭合权图：给每个点\(v\)分配一个点权\(w_v\)(可正可负)。最大权闭合图是一个点权之和最大的闭合图，即最大化\(\mathop{\sum}\limits_{v\in V^{'}}w_v\)。

1.3.2应用方法

给出的图一般是一个有向图，一个闭合图可以看做是一些点具有相互依赖的关系。因此对于有依赖关系，并且题目可以转化成给某些点赋权为正，某些点赋权为负的有依赖求最大权值和问题，考虑用最大闭合权图。

1.3.3构造

在原图的基础上增加源点\(s\)和汇点\(t\)；将原图中的每条有向边\(<u,v>\in E\)替换成容量为\(c(u,v)=\infty\)的有向边\(<u,v>\in E{'}\)；增加连接源\(s\)到原图的每个正点权\(v(w_v>0)\)的有向边\(<s,v>\in E^{'}\)，容量为\(c(s,v)=w_v\)；增加连接源\(t\)到原图的每个负点权\(v(w_v<0)\)的有向边\(<v,t>\in E^{'}\)，容量为\(c(s,v)=-w_v\)。建图时对应的反向边容量均为\(0\)。

最后的答案就等于原图所有正点权的和减去最小割，即\(ans=\mathop{\sum}\limits_{v\in V^{+}}w_v-c[S,T]\)

由于原图中的边容量为无穷，因此不会出现在最小割中，因此最后的割边一定是一组简单割。即每条割边都只和\(s\)关联或\(t\)关联。

1.4 最大密度子图

1.4.1定义：

• 定义一个无向图\(G=(V,E)\)的密度\(D\)为该图的边数\(|E|\)与该图的点数\(|V|\)的比值\(D=\frac{|E|}{|V|}\)。给出一个无向图\(G\)，其具有最大密度的子图\(G^{'}=(V^{'},E^{'})\)称为最大密度子图，即最大化\(D^{'}=\frac{E^{'}}{V^{'}}\)。一般是无向图

1.4.2 构造

解决方法是二分答案，假设当前二分的答案为\(g\)，原图的边数为\(M\)，那么建图方式如下：对原图中的所有边\(<u,v>\in E\)，建立容量为\(1\)的边\(<u,v>\in E{'}\)，其反向边容量也为\(1\)；建议源点\(s\)汇点\(t\)，\(s\)向原图中的每个点\(v\)连接容量为\(M\)的边，反向边容量为\(0\)；原图中每个点\(v\)向\(t\)连接正向容量为\(M+2g-degree[v]\)，发现容量为\(0\)的边。

void add(int u,int v,double c1,double c2)
{
    e[cnt].v=v,e[cnt].nxt=head[u],e[cnt].f=c1,head[u]=cnt++;
    e[cnt].v=u,e[cnt].nxt=head[v],e[cnt].f=c2,head[v]=cnt++;
}
void build(double g)
{
    memset(head,-1,sizeof head);
    cnt=0;
    for(int i=1;i<=m;i++) add(edge[i].a,edge[i].b,1,1);
    for(int i=1;i<=n;i++)
    add(S,i,m,0),add(i,T,m+2*g-dg[i],0);
}
double dinic(double g)
{
    build(g);
    double res=0,flow;
    while(bfs()) while(flow=find(S,inf)) res+=flow;
    return res;
}
int main()
{
    cin>>n>>m;
    S=0,T=n+1;
    for(int i=1;i<=m;i++)
    {
        int a,b;
        cin>>a>>b;
        edge[i]={a,b};
        dg[a]++,dg[b]++;
    }
    double l=0,r=m;
    while(l+1e-8<r)
    {
        double mid=(l+r)/2;
        double t=dinic(mid);
        if(m*n-t>0) l=mid;
        else r=mid;
    }
    dinic(l);
}

1.5 最小点权覆盖集与最大点权独立集

1.5.1定义

• 点覆盖集：是无向图\(G\)的一个点集，使得该图中所有边都至少有一个端点在该集合中。形式化定义就是点覆盖集\(V^{'}\in V\)，满足对于\(\forall (u,v)\in E\)，都有\(u\in V^{'}\)，\(v\in V^{'}\)至少一个成立。
• 点独立集：是无向图\(G\)的一个点集，使得任意两个在该集合中的点在原图中都不相邻。形式化定义就是点独立集为\(V^{'}\in V\)，满足对于\(\forall (u,v)\in E\)，都有\(u\in V^{'}\)与\(v\in V^{'}\)不同时成立。
• 最小点覆盖集：点数最少的点覆盖集
• 最大点独立集：点数最多的点独立集

以上问题都可以用二分图的最大匹配模型转化解决。

• 最小点权覆盖集：点权之和最小的点覆盖集
• 最大点权独立集：点权之和最大的点独立集

1.5.2最小点权覆盖集

• 分析：建立一个源点\(s\)和汇点\(t\)。\(s\)向每个\(X\)部连边，\(t\)向每个\(Y\)部连边，把二分图中的边看成是有向的。则任意一条从\(s\)到\(t\)的路径，一定具有\(s-u-v-t\)的形式。割的性质是不存在一条从s到t的路径，故路径上的三条边\(<s,u>,<u,v>,<v.t>\)中至少有一条边在割边中。利用技巧1，我们将\(c(u,v)=\infty\)，那么问题转为为\(<s,u>\)和\(<v,t>\)中至少一条在最小割，正好与点覆盖集限制条件符合(\(u\in V^{'},v\in V^{'}\)中至少一个成立)。而且目标是最小化点权之和，恰好也是最小割的优化目标。
• 建图：新建源点\(s\)和汇点\(t\)。每个\(X\)部向\(Y\)部连的边转化为连容量为\(\infty\)的有向边，\(s\)向每个\(X\)部的点\(u\)连容量为\(w_u\)的有向边，\(Y\)部的每个点\(v\)向点\(t\)连容量为\(w_v\)的有向边。最后答案就是最小割。

1.5.3最大点权独立集

• 分析：将点独立集的条件\(\forall (u,v)\in E\)，都有\(u\in V^{'}\)与\(v\in V^{'}\)不同时成立改写为布尔表达式：\(\neg(u\in V^{'}\wedge v\in V^{'})\)，化简得\(u\in \overset{-}{V^{'}}\vee v\in \overset{-}{V^{'}}\)，这个式子和点覆盖集的条件有点像。其实覆盖集和独立集是对偶问题，所以答案可以通过覆盖集求的。
• 最终答案就是总点权减去最小点权覆盖集的答案，即\(ans=\sum_{v\in V}w_v-\sum_{v\in V^{'}w_v}\)。

2.最大流

2.1无源汇上下界可行流

• 题目描述：给定有向图\(G=(V,E)\)，每条边都有一个流量上界和流量下界。要求一个满足流量限制的方案。

• 建图方式：记每条边的上界为\(up\)，下界为\(down\)

  • 先让每条边流满下界的流量，即将每条边的容量设置为\(up-down\)，下界设为\(0\)，但现在不满足流量守恒
  • 建立源点\(s\)和汇点\(t\)
  • 记录每个点\(u\)的流入流量\(in_u\)和流出流量\(out_u\)，以流满下界为标准
  • 如果\(in_u\ge out_u\)，说明\(u\)要向外多输出\(in_u-out_u\)的流量，从\(s\)向\(u\)连容量为\(in_u-out_u\)的边
  • 如果\(in_u\le out_u\)，说明\(u\)要向外多输入\(out_u-in_u\)的流量，从\(u\)向\(t\)连容量为\(out_u-in_u\)的边
  • 如果最后流量的最大值不等于从\(s\)中流出的满流，说明不满足流量守恒，因此无解

• 输入方案：对于原图的每条边，流量为反向边的流量\(f\)加上正向变的容量下界\(down\)。

• 代码：

  struct edges
  {
      int v,nxt,f,down;
  }e[M];
  void add(int u,int v,int down,int up)
  {
      e[cnt].v=v,e[cnt].nxt=head[u],e[cnt].f=up-down,e[cnt].down=down,head[u]=cnt++;
      e[cnt].v=u,e[cnt].nxt=head[v],e[cnt].f=0,head[v]=cnt++;
  }
  int main()
  {
      S=0,T=n+1;
      for(int i=1;i<=m;i++)
      {
          int a,b,down,up;
          cin>>a>>b>>down>>up;
          add(a,b,down,up);
          out[a]+=down;
          in[b]+=down;   // A[a]-=c,A[b]+=c;
      }
      int tot=0;
      for(int u=1;u<=n;u++)
        if(in[u]-out[u]>0) add(S,u,0,in[u]-out[u]) ,tot+=in[u]-out[u];
        else if(out[u]-in[u]>0) add(i,T,0,out[u]-in[u]);
        //if(A[u]>0) add(S,i,0,A[u]) ,tot+=A[u];
        //else if(A[u]<0) add(i,T,0,-A[u]);
        
        if(dinic()!=tot) cout<<"NO"<<endl;
        else
        {
            cout<<"YES"<<endl;;
            for(int i=0;i<m*2;i+=2)
            cout<<e[i^1].f+e[i].down<<endl;
        }
  }
  

2.2有源汇上下界最大流

• 题目描述：给定有向图\(G=(V,E)\)，每条边都有一个流量上界和流量下界，给定源点\(s\)和汇点\(t\)，求从\(S\)流到\(T\)的最大流。

• 建图方式：对于上下界的处理与无源汇上下界可行流相同，不同点在于对原图中\(s\)和\(t\)的处理

  • 建立虚拟源汇点\(S\)和\(T\)，对于上下界的限制建完边后，需要在原图中新建一条从汇点\(t\)到源点\(s\)，容量为\(\infty\)的边。然后以虚拟源汇点\(S\)和\(T\)跑一边最大流。
  • 如果跑出的最大流不等于从源点满流的值，说明流量不守恒，无解
  • 记从\(t\)到\(s\)连的容量为\(\infty\)的边的流量为\(res_1\)，然后断开这条边，把这条边的正反边容量设为\(0\)，然后从原来的源汇点\(s\)和\(t\)再跑一边最大流记答案为\(res_2\)，那么最终的最大流为\(res_1+res_2\)

• 代码：

  struct edges
  {
      int nxt,v,f;
  }e[M];
  void add(int u,int v,int f)
  {
      e[cnt].v=v,e[cnt].nxt=head[u],e[cnt].f=f,head[u]=cnt++;
      e[cnt].v=u,e[cnt].nxt=head[v],e[cnt].f=0,head[v]=cnt++;
  }
  int main()
  {
      S=0,T=n+1;
      cin>>n>>m>>s>>t;
      for(int i=1;i<=m;i++)
      {
          int a,b,c,d;
          cin>>a>>b>>c>>d;
          add(a,b,d-c);
          A[a]-=c,A[b]+=c;
      }
      int sum=0;
      for(int i=1;i<=n;i++)
      if(A[i]>0) add(S,i,A[i]),sum+=A[i];
      else if(A[i]<0) add(i,T,-A[i]);
      
      add(t,s,INF);
      
      if(dinic()!=sum) cout<<"No Solution"<<endl;
      else 
      {
          int res=e[cnt-1].f;
          S=s,T=t;
          e[cnt-1].f=e[cnt-2].f=0;
          cout<<res+dinic()<<endl;
      }
  }
  

2.3有源汇上下界最小流

• 题目描述：给定有向图\(G=(V,E)\)，每条边都有一个流量上界和流量下界，给定源点\(s\)和汇点\(t\)，求从\(S\)流到\(T\)的最小流。

• 建图方式：和有源汇上下界最大流几乎完全一样，不同点在于第二遍跑最大流时，利用\(S->T\)最大等价于\(T->S\)最小的转换，从\(t\)到\(s\)跑第二遍最大流，答案记为\(res_2\)，那么最终答案就是\(res_1-res_2\)

• 代码:

  //最后一部分不同
  int res=e[cnt-1].f;
  e[cnt-1].f=e[cnt-2].f=0;
  S=t,T=s;//S->T最小，等价于T->S最大
  cout<<res-dinic()<<endl;
  

2.4多源汇最大流

• 题目描述：给定一个包含\(n\) 个点 \(m\) 条边的有向图，并给定每条边的容量，边的容量非负。其中有 \(S_c\) 个源点，\(T_c\) 个汇点。图中可能存在重边和自环。求整个网络的最大流。
• 建图方法：
  • 建立超级源汇点\(S\)和\(T\)
  • \(S\)向原图中的每个源点\(s_i\)连容量为\(\infty\)的边，原图中的每个汇点\(t_i\)向\(T\)连容量为\(\infty\)的边，其他边正常连。
  • 最后跑一边最大流即可。

2.5 最小路径覆盖

• 最小路径覆盖是指，将原图分为若干条路径，任意两条路径不能有公共点，要使路径数量尽可能少
• 最小路径覆盖数=\(|G|\)-二分图最大匹配数，其中\(|G|\)表示图\(G\)中的边数
• 问题描述：给定有向图 \(G=(V,E)\) 。设 \(P\) 是 \(G\) 的一个简单路（顶点不相交）的集合。
  如果 \(V\) 中每个定点恰好在 \(P\) 的一条路上，则称 \(P\) 是 \(G\) 的一个路径覆盖。
  \(P\)中路径可以从\(V\)的任何一个定点开始，长度也是任意的,特别地,可以为\(0\)。
  \(G\)的最小路径覆盖是\(G\)所含路径条数最少的路径覆盖。
  设计一个有效算法求一个\(DAG\)(有向无环图)\(G\)的最小路径覆盖。
• 建图方法：每个点\(u\)拆成\(u_x,u_y\)，注意，这两个点之间不连边，然后对于原图的每条边\(<u,v>\)，从\(u_x\)向\(v_y\)连容量为\(1\)的边，源点\(S\)向每个点\(i_x\)连容量为\(1\)的边，每个点\(i_y\)向源点\(T\)连容量为\(1\)的边

2.6最长反链(一个点集)

• 定义：一张有向无环图DAG中的最长反链为一个集合\(S\subset V\)，满足对于\(S\)中任意两个不同的点\(u,v\in S\)(\(u\neq v\))，\(u\)不能到达\(v\)，\(v\)也不能到达\(u\)，且\(S\)的大小尽量大。
• Dilworth定理：最长反链数=最小链覆盖(最小路径覆盖)

3.费用流

3.1常见模型

• 二分图最优匹配
• 网格图模型
• 最大权不相交路径

4.常用技巧

4.1拆点（如果对点有限制）

• 拆点就是将一个点拆成入点和出点两个点，并在两个点之间建一条边。
• 拆点是为了实现对点的限制。

4.2常见模型

• 二维网格模型：对行和列有限制，建立二分图，\(X\)部是行，\(Y\)部是列，用连接所在行列的边表示对应格子的决策
• 流量平衡是费用流的模型：利用每个点流入流量等于流出流量来满足等式。
• 一维模型：一般的建模方式是直接建一条链：\(S\rightarrow x_1\rightarrow x_2\rightarrow...\rightarrow T\)，通过容量限制和流量平衡满足条件，利用费用流求答案
• 对于有依赖、捆绑、偏序关系的问题，考虑转化为最大权闭合子图，利用最小割求解
• 二维网格模型，如果每次操作的是相邻的格子，可以看做是黑白染色，根据格子横纵坐标和的奇偶性染色。

5.模板

5.1Dinic

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
const int N,M,INF;
int n,m,S,T,cnt;
int head[N],d[N],cur[N];
struct edges
{
	int v,nxt,f;
}e[M*2];
void add(int u,int v,int f)
{
	e[cnt].v=v,e[cnt].nxt=head[u],e[cnt].f=f,head[u]=cnt++;
	e[cnt].v=u,e[cnt].nxt=head[v],e[cnt].f=0,head[v]=cnt++;
}

bool bfs()
{
	memset(d,-1,sizeof d);
	queue<int>q;
	q.push(S);
	d[S]=0,cur[S]=head[S];
	while(q.size())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];~i;i=e[i].nxt)
		{
			int v=e[i].v,f=e[i].f;
			if(d[v]==-1&&f)
			{
				d[v]=d[u]+1;
				cur[v]=head[v];
				if(v==T) return true;
				q.push(v);
			}
		}
	}
	return false;
}
int find(int u,int limit)
{
	if(u==T) return limit;
	int flow=0;
	for(int i=cur[u];~i&&flow<limit;i=e[i].nxt)
	{
		cur[u]=i;
		int v=e[i].v,f=e[i].f;
		if(d[v]==d[u]+1&&f)
		{
			int t=find(v,min(f,limit-flow));
			if(!t) d[v]=-1;
			e[i].f-=t,e[i^1].f+=t,flow+=t;
		}
	}
	return flow;
}
int dinic()
{
	int ans=0,flow;
	while(bfs()) while(flow=find(S,INF)) ans+=flow;
	return ans;
}

int main()
{
    memset(head,-1,sizeof head);
    cin>>n>>m>>S>>T;
	for(int i=1;i<=m;i++)
	{
		int u,v,f;
		cin>>u>>v>>f;
		add(u,v,f);
    }
	cout<<dinic()<<endl;
	return 0;	
}

5.2 费用流

//最小费用最大流，将EK算法的BFS换成SPFA，若存在负环，该模板不适用，要加入消圈发法 

#include <iostream>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;
const int N=5005,M=50005*2,inf=1e8;
int n,m,S,T,cnt;
int head[N],d[N],st[N],pre[N],incf[N];
struct edges
{
    int v,nxt,f,c;
}e[M];
void add(int u,int v,int f,int c)
{
     e[cnt].v=v,e[cnt].nxt=head[u],e[cnt].f=f,e[cnt].c=c,head[u]=cnt++;
     e[cnt].v=u,e[cnt].nxt=head[v],e[cnt].f=0,e[cnt].c=-c,head[v]=cnt++;
}
bool spfa()
{
    memset(d,0x7f,sizeof d);
    memset(incf,0,sizeof incf);
    queue<int>q;
    q.push(S);
    d[S]=0,incf[S]=inf;
    while(q.size())
    {
        int u=q.front();
        q.pop();
        st[u]=0;
        for(int i=head[u];~i;i=e[i].nxt)
        {
            int v=e[i].v,f=e[i].f,c=e[i].c;
            if(f&&d[v]>d[u]+c)
            {
                d[v]=d[u]+c;
                pre[v]=i;
                incf[v]=min(incf[u],f);
                if(!st[v])
                {
                    st[v]=1;
                    q.push(v);
                }
                
            }
        }
    }
    return incf[T]>0;
}
void EK(int &flow,int &cost)
{
    flow=cost=0;
    while(spfa())
    {
        int t=incf[T];
        flow+=t,cost+=t*d[T];
        for(int i=T;i!=S;i=e[pre[i]^1].v)
        {
            e[pre[i]].f-=t,e[pre[i]^1].f+=t;
        }
    }
}
int main()
{
    memset(head,-1,sizeof head);
    cin>>n>>m>>S>>T;
    for(int i=1;i<=m;i++)
    {
        int u,v,f,c;
        cin>>u>>v>>f>>c;
        add(u,v,f,c);
    }
    int flow,cost;
    EK(flow,cost);
    cout<<flow<<" "<<cost<<endl;
    return 0;
}

dji优化

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int N=5005,M=50005*2;
const ll inf=1e18;
int n,m,S,T,cnt;
int head[N],st[N],pre[N],incf[N];
ll d[N];
struct edges
{
    int v,nxt,f ,c;
}e[M];
void add(int u,int v,int f,int c)
{
     e[cnt].v=v,e[cnt].nxt=head[u],e[cnt].f=f,e[cnt].c=c,head[u]=cnt++;
     e[cnt].v=u,e[cnt].nxt=head[v],e[cnt].f=0,e[cnt].c=-c,head[v]=cnt++;
}
bool dji()
{
    for(int i=0;i<=n+1;i++) d[i]=inf;
    memset(incf,0,sizeof incf);

    priority_queue<pair<ll,int>>q;
    q.push({0,S});
    d[S]=0;
    incf[S]=1e9;
    while(q.size())
    {
        auto t=q.top();
        q.pop();
        if(d[t.second]!=-t.first) continue;
        for(int i=head[t.second];~i;i=e[i].nxt)
        {
            int v=e[i].v,f=e[i].f;
            ll c=e[i].c;
            if(f&&d[v]>d[t.second]+c)
            {
                d[v]=d[t.second]+c;
                pre[v]=i;
                incf[v]=min(incf[t.second],f);
                q.push({-d[v],v});
            }
        }
    }
    return incf[T]>0;
}
void EK(int &flow,ll &cost)
{
    flow=0,cost=0;
    while(dji())
    {
        int t=incf[T];
        flow+=t,cost+=1LL*t*d[T];
        for(int i=T;i!=S;i=e[pre[i]^1].v)
        {
            e[pre[i]].f-=t,e[pre[i]^1].f+=t;
        }
    }
}

参考链接

网络流建模方式总结

国家集训队胡泊涛最小割应用

​