传送门
题意：有 \(n\) 个队友和 \(m\) 个敌人，每个队友 \(i\) 有 \(a_i\) 颗子弹。敌人 \(j\) 有 \(b_j\) 颗子弹。
队友击杀敌人，必须 \(a_i>b_j\)，然后会获得 \(a_i-b_j+w_j\) 的收益。（\(w_j\): 每个敌人都有一个参数）
每个队友只能打一个敌人，可以不打。求最大收益。
【费用流模型】
上面那一排点表示队友，下面一排点表示敌人。若队友 \(a_i\) 能打敌人 \(b_j\)，连边 \(a_i\rightarrow b_j\)，容量 \(1\) 费用 \(0\)。
\(S\rightarrow a_i\)，容量 \(1\) 费用 \(a_i\)。\(b_j\rightarrow T\)，容量 \(1\) 费用 \(c_j=-b_j+w_j\)。注意这个费用可能是负数。
求最大费用任意流。
【模拟费用流】
任意流的题目一般都是用增量算法。
直接来不好弄，因为每个队友能杀什么敌人是随机的，我们还要遍历一遍。
可以观察一个性质：如果把队友和敌人都按子弹数量从小到大排序，每个队友打的都是一个前缀。
也就是这样：
考虑新增加点 \(a_n\)。
新的增广路有哪几种？
第一条增广路的收益是 \(a_n+c_k\)，要求 \(c_k\rightarrow T\) 的边没用过。
第二条增广路的收益是 \(a_n+c_?\)，要求 \(c_?\rightarrow T\) 的边没用过。
那这两种有什么区别呢？其实没有区别。较复杂的增广路只是让每个队友匹配的敌人变了。但是其实哪个队友匹配哪个敌人没有任何影响。
所以可以统合为：\(a_n+c_?\)，要求 \(c_?\rightarrow T\) 没用过。
然后考虑环。
一种：
收益是 \(a_n-a_k\)。要求 \(S\rightarrow a_k\) 用过。
两种：
收益是 \(a_n+c_n-(a_k+c_k)\)，因为是最大费用任意流，已经应用的增广路费用一定是正数，所以 \(a_k+c_k>0\)，还不如直接应用增广路。
点击查看代码
#include
using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
int n, m;
ll a[N];
int pos[N]; //a[i]能打1~pos[i]
struct Enemy {
ll b, w, c;
} e[N];
bool cmp(Enemy a, Enemy b) {
return a.b < b.b;
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= m; i++) {
cin >> e[i].b >> e[i].w;
e[i].c = -e[i].b + e[i].w;
}
sort(a + 1, a + n + 1);
sort(e + 1, e + m + 1, cmp);
for (int i = 1, j = 0; i <= n; i++) {
while (j + 1 <= m && e[j + 1].b < a[i])
j++;
pos[i] = j;
}
ll ans = 0;
priority_queue
priority_queue
for (int i = 1; i <= n; i++) {
for (int j = pos[i - 1] + 1; j <= pos[i]; j++)
q.push(e[j].c);
ll tmp1 = -1, tmp2 = -1;
if (!q.empty())
tmp1 = a[i] + q.top();
if (!q2.empty())
tmp2 = a[i] - q2.top();
if (tmp1 < 0 && tmp2 < 0)
continue;
if (tmp1 > tmp2) {
ans += tmp1;
q.pop();
q2.push(a[i]);
}
else {
ans += tmp2;
q2.pop();
q2.push(a[i]);
}
}
cout << ans << endl;
return 0;
}