自动搬运

查看原文

来自洛谷，原作者为

	Morpheuse 学长说，多读博客少做题，套路就是力量.

搬运于2025-08-24 22:01:17，当前版本为作者最后更新于2022-03-30 21:50:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

并不需要上下界网络流.

题意

用 $m$ 条可相交的路径覆盖每个点 $v_i$ 次.

做法

对于每个点 $i$ 有且仅有 $v_i$ 次进入，也有 $v_i$ 次离开.

$s$ 为源点， $t$ 为汇点.

以下除特殊说明，费用均为 $0$.

$s\to i$ 流量为 $v_i$ 表示一定有 $v_i$ 次离开.

$i + n \to t$ 流量为 $v_i$ 表示必须要有 $v_i$ 次进入.

因为 $m$ 个人都可以从任意点开始.

相当于我们有 $m$ 次无需费用即可进入的权限.

所以我们新建一个点 $M$.

$s\to M$ 流量为 $m$ 表示有 $m$ 次无需费用进入的权限.

对于每个 $i , M\to i + n$ 流量为 $inf$ 表示可以从无需费用进入 $i$.

对于每条边 $(u,v,w)$ 建边 $u\to v + n$ 流量为 $inf$ , 费用为 $w_i$.

最小费用最大流即可.

代码

scanf("%d%d", &n,&m);
for(int i = 1 ; i <= n ; ++ i) scanf("%d", &a[i]);
s = 0 , t = maxn - 10;

/*
源点.
数组大小.
初始化. 
*/
int ss = maxn - 11;
add(s , ss , m , 0);
for(int i = 1 ; i <= n ; ++ i)
	add(ss , i + n , inf , 0);
for(int i = 1 ; i <= n ; ++ i)
	add(s , i , a[i] , 0);
for(int i = 1 ; i <= n ; ++ i)
	add(i + n , t , a[i] , 0);
for(int i = 1 ; i <= n - 1 ; ++ i)
{
	for(int j = 1 ; j <= n - i ; ++ j)
	{
		int x;
		scanf("%d", &x);
		if(x == -1) x = inf;
		add(i , i + j + n , inf , x);
	}
}
printf("%d", cot);