P4553 80人环游世界 题解
Morpheuse
·
·
题解
并不需要上下界网络流.
题意
用 m 条可相交的路径覆盖每个点 v_i 次.
做法
对于每个点 i 有且仅有 v_i 次进入，也有 v_i 次离开.
以下除特殊说明，费用均为 $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$.
最小费用最大流即可.
## 代码
```cpp
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);
```