网络流建图总结

1.最小割

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

1.1割的性质

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

1.2技巧

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

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

1.3.1定义

• 闭合图定义：定义个一有向图\(G=(V,E)\)的闭合图是该有向图的一个点集，且该点集的所有出边都还指向该点集。即闭合图内的任意点的任意后继也一定在闭合图中。形式化定义就是：闭合图是这样的一个点集\(V^{'}\in V\)，满足对于\(\forall u\in V^{'}\)引出的\(\forall \in E\)，必有\(v\in V^{'}\)成立。还有一种定义：满足对于\(\forall \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\)；将原图中的每条有向边\(\in E\)替换成容量为\(c(u,v)=\infty\)的有向边\(\in E{'}\)；增加连接源\(s\)到原图的每个正点权\(v(w_v>0)\)的有向边\(\in E^{'}\)，容量为\(c(s,v)=w_v\)；增加连接源\(t\)到原图的每个负点权\(v(w_v<0)\)的有向边\(\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\)，那么建图方式如下：对原图中的所有边\(\in E\)，建立容量为\(1\)的边\(\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-80) 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的路径，故路径上的三条边\(,,\)中至少有一条边在割边中。利用技巧1，我们将\(c(u,v)=\infty\)，那么问题转为为\(\)和\(\)中至少一条在最小割，正好与点覆盖集限制条件符合(\(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"<

#include 
#include 
#include 
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);
	queueq;
	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>n>>m>>S>>T;
	for(int i=1;i<=m;i++)
	{
		int u,v,f;
		cin>>u>>v>>f;
		add(u,v,f);
    }
	cout<

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



#include 
#include 
#include 
#include 
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);
    queueq;
    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<