题解【CF1316E Team Building】网络流做法

题目传送门。

一眼费用流。

然后发现题解区竟然全是状压 DP？？？？？

推销一下本题状压 DP 的题解。

那么我就来 yy 一下我的网络流做法吧，我会尽量把网络流的想法讲得自然一点。

考虑将所有人按照 \(a_i\) 从大到小排序，那么贪心的考虑，如果一个人不去当球员，那么能当观众就当观众。

这里就有了一个隐藏的条件了：不管你 \(p\) 个球员选的谁，观众一定是前 \(\left(p+k\right)\) 个人中，没去当球员的贡献最大的前 \(k\) 个，当然也至少需要 \(k\) 个人，所以我们得到观众选取的范围 \([k,p+k]\)。

我们钦定前 \(b\) 个人全部当观众，其中 \(b\in [k,p+k]\)，那么肯定需要调整一些人当球员。

那么我们总体思路就出来了，首先钦定收益为前 \(b\) 个人都当观众的收益，然后加上 \([1,n]\) 中球员的收益，然后减去 \([1,b]\) 中，由观众变成球员的收益。

具体如何选取呢？

我们对于 \(i\in [1,b]\) 选出若干人当球员，在 \(i\in (b,n]\) 中选出若干人当球员，其余人当观众，若观众没有空位，那么就摆烂。

那么在 \([1,b]\) 中选出多少人当球员呢？

显然答案是固定的，只能是 \((b-k)\) 个，因为我们一开始固定，观众只能在 \([1,b]\) 中选。有 \(k\) 个人当观众，那么就有 \(b-k\) 个人当球员。

而我们一共要找 \(p\) 个人当球员，\([1,b]\) 中有 \(b-k\) 个球员，所以 \((b,n]\) 中一共有 \(p-(b-k)\) 个球员。

个数与花费两层限制，不就是费用流吗！

下文记 \((u,v,f,w)\) 表示一条从 \(u\) 到 \(v\)，容量为 \(f\)，流量为 \(w\) 的弧。

我们建立两个源点 \(A,B\)，表示 \([1,b]\) 点的集合，和 \((b,n]\) 点的集合。初始对于 \(i\in [1,n]\)，连一条 \((A,i,1,0)\) 的边，同理，对于 \(i\in (b,n]\)，连一条 \((B,i,1,0)\)。

然后建立总源 \(S\)，连 \((S,A,b-k,0)\) 和 \((S,B,p-b+k,0)\) 的边。

\(A,B\) 的意义到这里也就清晰明了了，它固定了两个集合中，当球员的人数。

之后就可以暴力连边啦。

连边的思路是，每一个 \([1,b]\) 的观众都有可能成为球员，那么暴力把所有可能连上，跑一遍网络流只会留下合法的解。

那么对于 \(i\in [1,b]\) 和 \(j\in [1,p]\)，连一条 \((i,j+n,1,-a_i+s_{i,j})\) 的边，这里的意思，若 \(i\) 变成球员，那么需要减掉一开始算在观众里 \(a_i\) 的贡献，然后加上变成球员的贡献 \(s_{i,j}\)。

然后对于另一半 \(i\in (b,n]\)，练一天 \((i,j+n,1,s_{i,j})\) 的边，因为这里的 \(i\) 一开始没有被钦定成观众，直接算它成为球员的贡献即可。

最后每一个球队的位置连向 \(T\) 即可。

但是这道题可能需要 \(\text{zkw}\) 费用流，我的 \(\text{EK}\) 被卡了，但是我偷懒吸一口臭氧就卡过了（

代码想要的人私信，不放了。

求赞/kel