院科技文化节高级组 C.随时随地, 脉动回来(最小/最大费用流裸题)

思路来源

舟亢学长

题解

裸最小费用最大流（最短路）

裸最大费用最大流（负权最短路再取反）

心得

本来比赛的时候有时间敲 预估自己30min

结果赛后补题敲了1h tm还WA了好几发

请学长debug结果是数组开小了GG

我怎么这么菜啊

还是对费用流理解不深啊

弧优化+SLF优化的SPFA是不可能被卡掉的啊

这样看来，手敲板子的学弟还真是遥不可及啊……

不禁让人怀念过目不忘的初中高中生涯……

如今已是按板子敲都能出各种bug的老年人了……

代码

#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn=110;//点的数量 
const int maxm=50005;//2*maxn*maxn+2*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];
ll tot;//总费用 
int head[maxn],cnt;
int n,m;
int s,t;
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()
{
	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,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,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())
	{
		vis[t]=1;
		while(vis[t])
		{
			memset(vis,0,sizeof vis);
			ans+=dfs(s,INF,tot);
		}
	}
	return ans;
} 
void init()
{
	cnt=0;tot=0;
	for(int i=0;i<2*maxn;++i)
	dis[i]=INF;
	memset(head,-1,sizeof head);
	memset(vis,0,sizeof vis);
}
int main()
{
	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);
    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;
}