网络流求最小费用特解（网络流解线性规划）学习笔记

由于网络流图中除了源点和汇点外，其它节点都满足流入的流量等于流出的流量。所以我们可以通过把若干等式转换成图来求解最小费用的特解，不等式变形做一下差分变成等式也可以求。

具体的做法是，先把每个等式都变形、化简，令每一个未知数都在且仅在两个等式里出现，且系数分别为 $+1$ 和 $-1$。

接下来：

• 建立源点、汇点，并对每一个等式建一个点

• 如果第 $i$ 个不等式右边的常量为非负整数 $w_i$，那么从 $i$ 向汇点连流量为 $w_i$，费用为 $0$ 的边表示多余数量被吸走；如果第 $i$ 个不等式右边的常量为负整数 $w_i$，那么从源点向 $i$ 连流量为 $-w_i$，费用为 $0$ 的边表示少掉的流量被补充

• 如果未知数 $x_i$ 在等式 $j$ 里的系数为 $-1$，在等式 $k$ 里的系数为 $+1$，并且这个未知数在最终计算答案的时候的系数为 $c_i$，那么从 $j$ 向 $k$ 连流量为 $\inf$，费用为 $c_i$ 的边，表示这个未知数的值从多出来的等式流向少掉的等式，且这个未知数增大需要收取费用（计算进答案）

最后判断有无可行解即判断是否满流，而最小解即为最小费用最大流。

例题

先假设共 $3$ 天，第 $i$ 天招募 $p_i$ 人，共有 $3$ 类志愿者：

• 第一类：从第 $1$ 天到第 $3$ 天，费用为 $c_1$，招募了 $b_1$ 人

• 第二类：从第 $2$ 天到第 $3$ 天，费用为 $c_2$，招募了 $b_2$ 人

• 第三类：从第 $1$ 天到第 $3$ 天，费用为 $c_3$，招募了 $b_3$ 人

可以列出如下不等式：

$p_1=b_1+b_3\ge a_1$

$p_2=b_1+b_2+b_3\ge a_2$

$p_3=b_1+b_2\ge a_3$

考虑转化成等式，设第 $i$ 天招募的人数超出最小人数 $d_i$ 人，显然 $d_i\ge0$，那么有：

$p_1=b_1+b_3=a_1+d_1$

$p_2=b_1+b_2+b_3=a_2+d_2$

$p_3=b_1+b_2=a_3+d_3$

相邻两个等式相减（默认第 $0$ 个和第 $4$ 个等式为 $0$）:

$p_1=b_1+b_3=a_1+d_1$

$p_2-p_1=b_2=a_2-a_1+d_2-d_1$

$p_3-p_2=-b_3=a_3-a_2+d_3-d_2$

$-p_3=-b_1-b_2=-a_3-d_3$

整理，消去 $p$，得：

$b_1+b_3-a_1-d_1=0$

$b_2+a_1-a_2+d_1-d_2=0$

$-b_3+a_2-a_3+d_2-d_3=0$

$-b_1-b_2+a_3+d_3=0$

容易发现，这样构造可以令等式满足条件，所以可以建图跑最小费用最大流求解了。

建图方式如下：

• 建立源点、汇点和 $n+1$ 个等式点

• 处理掉未知数 $d_i$ 和 $a_i$，$i$ 向 $i+1$ 连一条流量为 $\inf$，费用为 $0$ 的边

• 处理掉 $b_i$，对于第 $i$ 类志愿者，从 $s_i$ 向 $t_i$ 连一条流量为 $\inf$，费用为 $c_i$ 的边，表示答案贡献式里的系数计算

• 从源点向 $1$ 连一条流量为 $\inf$，费用为 $0$ 的边；从 $n+1$ 向汇点连一条流量为 $\inf$，费用为 $0$ 的边，让整张图“流起来”

最后跑最小费用最大流求出最小费用即可。

代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>

using namespace std;

const int S=5000005,MS=100005;
const long long inf=1000000007;

int n,m,s,t;
int esum,to[S],nxt[S],h[MS];
long long c[S],cost[S];
long long dis[MS];
int cur[MS];
bool vis[MS];
long long maxflow,mincost;

inline void init()
{
	esum=1;
	memset(h,0,sizeof(h));
	s=0;
	t=n+2;
}

inline void add(int x,int y,long long w,long long v)
{
	to[++esum]=y;
	c[esum]=w;
	cost[esum]=v;
	nxt[esum]=h[x];
	h[x]=esum;
}

inline bool spfa()
{
	memset(dis,127,sizeof(dis));
	memset(vis,0,sizeof(vis));
	long long inf=dis[0];
	queue<int> q;
	dis[s]=0;
	vis[s]=true;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=false;
		for(int i=h[u];i;i=nxt[i])
		{
			int v=to[i];
			long long w=cost[i];
			if(c[i]>0&&dis[u]+w<dis[v])
			{
				dis[v]=dis[u]+w;
				if(!vis[v])
				{
					vis[v]=true;
					q.push(v);
				}
			}
		}
	}
	return dis[t]<inf;
}

long long dfs(int u,long long w)
{
	if(u==t)
	{
		return w;
	}
	vis[u]=true;
	long long sum=0;
	for(int &i=cur[u];i;i=nxt[i])
	{
		int v=to[i];
		if(c[i]>0&&dis[v]==dis[u]+cost[i]&&!vis[v])
		{
			long long re=dfs(v,min(w,c[i]));
			mincost+=re*cost[i];
			c[i]-=re;
			c[i^1]+=re;
			w-=re;
			sum+=re;
			if(w==0)
			{
				break;
			}
		}
	}
	vis[u]=false;
	return sum;
}

inline void mcmf()
{
	mincost=0;
	maxflow=0;
	while(spfa())
	{
		for(int i=s;i<=t;i++)
		{
			cur[i]=h[i];
		}
		maxflow+=dfs(s,1e17);
	}
}

int main()
{
	scanf("%d%d",&n,&m);
	init();
	add(s,1,inf,0);
	add(1,s,0,0);
	add(n+1,t,inf,0);
	add(t,n+1,0,0); 
	for(int i=1;i<=n;i++)
	{
		long long x;
		scanf("%lld",&x);
		add(i,i+1,inf-x,0);
		add(i+1,i,0,0);
	}
	for(int i=1;i<=m;i++)
	{
		int l,r;
		long long need;
		scanf("%d%d%lld",&l,&r,&need);
		add(l,r+1,1e17,need);
		add(r+1,l,0,-need);
	}
	mcmf();
	printf("%lld\n",mincost);
	return 0;
}