目录

• 模板
• 直接应用
• 费用流之二分图最有匹配
• 最大权不相交路径
• 网格图模型
• 拆点
• 费用流之上下界可行流

模板

EK

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){ if(ch=='-') f=-1;ch=getchar(); }
	while(ch>='0'&&ch<='9'){ x=(x<<1)+(x<<3)+(ch^48);ch=getchar(); }
	return x*f;
}
const int Maxn=5e3+5,Maxm=5e4*2+500,INF=1e8;
struct edge{
	int to,nxt,f,cost;
}e[Maxm];
queue<int> q;
int n,m,S,T,tot=1;
int head[Maxn],incf[Maxn],pre[Maxn],dis[Maxn];
bool vis[Maxn];
inline void add(int u,int v,int c,int d)
{
	e[++tot].to=v; e[tot].nxt=head[u]; head[u]=tot; e[tot].f=c; e[tot].cost=d;
	e[++tot].to=u; e[tot].nxt=head[v]; head[v]=tot; e[tot].f=0; e[tot].cost=-d;
}

inline bool spfa()
{
	memset(dis,0x3f,sizeof dis);
	memset(incf,0,sizeof incf);
	q.push(S);
	incf[S]=INF; dis[S]=0;
	while(!q.empty())
	{
		int now=q.front();q.pop();
		vis[now]=0;
		for(int i=head[now];i>1;i=e[i].nxt)
		{
			int nx=e[i].to;
			if(dis[nx]>dis[now]+e[i].cost&&e[i].f)
			{
				dis[nx]=dis[now]+e[i].cost;
				incf[nx]=min(incf[now],e[i].f);
				pre[nx]=i;
				if(!vis[nx])
				{
					vis[nx]=1;
					q.push(nx);
				}
			}
		}
	}
	return incf[T]>0;
}

inline void EK(int& flow,int& cost)
{
	flow=0; cost=0;
	while(spfa())
	{
		int t=incf[T];
		flow+=t; cost+=t*dis[T];
		for(int i=T;i!=S;i=e[pre[i]^1].to)
		{
			e[pre[i]].f-=t;
			e[pre[i]^1].f+=t;
		}
	}
}

int main()
{
	n=read(); m=read(); S=read(); T=read();
	for(int i=1,a,b,c,d;i<=m;i++)
	{
		a=read(); b=read(); c=read(); d=read();
		add(a,b,c,d);
	}
	int flow,cost;
	EK(flow,cost);
	printf("%d %d",flow,cost);
	return 0;
}

直接应用

• 建图：S连左侧点 ( a i j , 0 ) (a_{ij},0) (aij​,0)，右侧点连T ( b i j , 0 ) (b_{ij},0) (bij​,0)，左侧点和右侧点之间连 ( I N F , C i j ) (INF,C_{ij}) (INF,Cij​)
• 方法：跑最大费用最大流
• 输出方案：看中间的边哪些的反向边容量大于0，且满足点的限制

费用流之二分图最有匹配

• 建图：S连左侧点 ( a i j , 0 ) (a_{ij},0) (aij​,0)，右侧点连T ( b i j , 0 ) (b_{ij},0) (bij​,0)，左侧点和右侧点之间连 ( I N F , C i j ) (INF,C_{ij}) (INF,Cij​)
• 方法：跑最大费用最大流，或者，最小费用最大流
• 输出方案：枚举中间的边，看容量

最大权不相交路径

• 建图：拆点，把费用和流量限制加在入点和出点之间的边上
• 方法：跑最大费用最大流
• 输出方案：看每个边的流量，如果这个边流量是INF，就看它的反向边

网格图模型

• 建图：可以找规律然后使用get（函数）给每一个点赋上唯一编号。当然，也可以用 f l a g flag flag数组标记一下，判断这个点是否已经有编号，如果有就返回这个值，如果没有，就赋值为++cnt
• 方法：如果权值本来就在边上，就把费用加在边上，否则，就拆点
• 输出方案：看流量

拆点

• 建图：如果一个点有很多限制和方案，可以考虑吧这个点拆开，然后把不同的方案转移加不同的边，就可以利用这个跑最大流，求出结果。
• 方法：有可能不是为了限制一个点，而是像分层图一样，把这个流分类分析
• 输出方案：看流量

费用流之上下界可行流

• 建图：和最大流的上下界是一样的，看 A [ i ] A[i] A[i]的正负，
  如果 A [ i ] > 0 A[i]>0 A[i]>0从S向这个点建A[i]的边，反之<0，向 T建 a b s ( A [ i ] ) abs(A[i]) abs(A[i])的边
• 方法：新图上的最大流就是原图的可行流，在可行流里找到一种可行方案，算出（原图）最小费用最大流=>（新图）最小费用可行流
• 输出方案：看答案要求的边上的流量和费用