博客

板子（以院赛费用流裸题为例）

一般把超级源点s赋0，超级汇点t赋1+所有点的个数num

连边时调用add2函数，正向边流量满值且费用为正，负向边流量为0且费用为负

开点时点和边权的数组别开小了，考虑最极限的情况来开数组

这个板子是从汇点反向spfa的，引入了势的概念，加入了spfa的双端队列优化

调用maxflow(源点，汇点，费用值）的函数，函数返回值为最大流

最小费用最大流，正费用建图跑

最大费用最大流，负费用建图，

求出最小的负的费用，其绝对值就是最大的正费用

板子是针对有向边的情形，

无向边的图，需要拆分成两条有向边，即两次加边。

代码

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=110;//点的数量 应为 两边点数总和+2
const int maxm=50005;//2*maxn*maxn+4*maxn 源点出maxn条 汇点入maxn条 中间点两两连 
const ll INF=1e18; 
struct edge
{
   int u,v;
   ll cos,nex,w;
}e[maxm];
ll vis[2*maxn],dis[2*maxn];
ll l[2*maxn],r[2*maxn],cost[2*maxn][2*maxn];
int head[2*maxn],cnt;
void add(int u,int v,ll w,ll cos)
{
	e[cnt].v=v;
	e[cnt].w=w;
	e[cnt].cos=cos;
	e[cnt].nex=head[u];
	head[u]=cnt++;
}
void add2(int u,int v,ll w,ll cos)
{
	add(u,v,w,cos);
	add(v,u,0,-cos);
}
bool spfa(int s,int t)
{
	for(int i=0;i<2*maxn;++i)
	dis[i]=INF;
	memset(vis,0,sizeof vis);
	vis[t]=1;
	dis[t]=0;
	deque<int>q;
	q.push_back(t);
	while(!q.empty())
	{
		int u=q.front();
		vis[u]=0;
		q.pop_front();
		for(int i=head[u];~i;i=e[i].nex)
		{
			int v=e[i].v;
			if(e[i^1].w>0&&dis[v]>dis[u]-e[i].cos)
			{
				dis[v]=dis[u]-e[i].cos;
				if(!vis[v])
				{
					vis[v]=1;
					if(!q.empty()&&dis[v]<dis[q.front()])
					q.push_front(v);
					else q.push_back(v);
				}
			}
		}
	}
	return dis[s]<INF;
}
ll dfs(int u,int t,ll low,ll &tot)
{
	vis[u]=1;
	if(u==t)return low;
	ll ans=0;
	for(int i=head[u];~i;i=e[i].nex)
	{
		int v=e[i].v;
		if(!vis[v]&&e[i].w&&dis[v]==dis[u]-e[i].cos)
		{
			ll now=dfs(v,t,min(low,e[i].w),tot);
			if(now>0)
			{
				tot+=e[i].cos*now;
				low-=now;
				ans+=now;
				e[i].w-=now;
				e[i^1].w+=now;
				if(low==0)break;
			}
		}
	}
	return ans;
}
ll max_flow(int s,int t,ll &tot)//tot返回费用 函数返回值为最大流 
{
	ll ans=0;
	while(spfa(s,t))
	{
		vis[t]=1;
		while(vis[t])
		{
			memset(vis,0,sizeof vis);
			ans+=dfs(s,t,INF,tot);
		}
	}
	return ans;
} 
void init()
{
	cnt=0;
	for(int i=0;i<2*maxn;++i)
	dis[i]=INF;
	memset(head,-1,sizeof head);
	memset(vis,0,sizeof vis);
}
int main()
{
	ll tot;//总费用 
	int n,m,s,t;
    tot=0;
	init();
    scanf("%d%d",&m,&n);
    //超级源 超级汇
    s=0;t=m+n+1; 
    //左供货 右需求
    for(int i=1;i<=m;++i)
    {
    	scanf("%lld",&l[i]);
	    add2(s,i,l[i],0);//超级源点 
    }
    for(int i=1;i<=n;++i)
	{
	    scanf("%lld",&r[i]);
        add2(m+i,t,r[i],0);//超级汇点
	} 
    for(int i=1;i<=m;++i) 
    {
    	for(int j=1;j<=n;++j)
    	{
    		scanf("%lld",&cost[i][j]);
    		add2(i,m+j,l[i],cost[i][j]);//l[i]的流量 dis的费用 
    	}
    }
    max_flow(s,t,tot);
    printf("%lld\n",tot);
    tot=0;
    init();
    for(int i=1;i<=m;++i)
    {
	    add2(s,i,l[i],0);//超级源点 
    }
    for(int i=1;i<=n;++i)
	{
        add2(m+i,t,r[i],0);//超级汇点
	} 
    for(int i=1;i<=m;++i) 
    {
    	for(int j=1;j<=n;++j)
    	{
    		add2(i,m+j,l[i],-cost[i][j]);//l[i]的流量 dis的费用 
    	}
    }
    max_flow(s,t,tot);
    printf("%lld\n",-tot);
   return 0;
}