题意
招募若干经理。
当经理\(i\)和经理\(j\)同时被雇佣时,所赚得的利润增加\(E{i,j}\)。
雇佣经理\(i\)需要花费一定的金钱\(A_i\)。
然而,没有被雇佣的人会使得所赚得的利润减少\(E_{i,j}\)(\(i\)被雇佣,\(j\)未被雇佣时)。
求最大净利润。
思路
先设利润=\(\sum_{i=1}^{n}\sum_{j=1}^{n}E_{i,j}\)
对于经理\(i\),连\(S\to i\),容量为\(A_i\)的边;连\(i\to T\),容量为\(\sum_{j=1}^{n}E_{i,j}\)的边。
求最小割,即雇佣/不雇佣对利润造成的影响。
考虑没雇佣的人造成的影响。
对于两个经理\(i,j\),只雇佣其中之一会亏损\(2*E_{i,j}\)(一份是两人都雇佣可获得的,一份是额外亏损的,都要减去)。
那么连边\(i\to j\),容量为\(2*E_{i,j}\)。当两人只有一人雇佣,这条边就要割去。
代码
#include <queue>
#include <cstdio>
#include <algorithm>
int n, S, E, tot = 1, ans;
int ver[2100001], next[2100001], head[1001], edge[2100001], lev[1001], cur[1001];
void add(int u, int v, int f) {
ver[++tot] = v, next[tot] = head[u], edge[tot] = f, head[u] = tot;
ver[++tot] = u, next[tot] = head[v], edge[tot] = 0, head[v] = tot;
}
int dfs() {
std::queue<int> q;
for (int i = 1; i <= E; i++)
lev[i] = 0, cur[i] = head[i];
lev[S] = 1;
q.push(S);
int v;
while (q.size()) {
int u = q.front();
q.pop();
for (int i = head[u]; i; i = next[i])
if (edge[i] && !lev[v = ver[i]]) {
lev[v] = lev[u] + 1;
q.push(v);
}
}
return lev[E];
}
int dinic(int u, int flow) {
if (u == E)
return flow;
int res = 0, delta, v;
for (int &e = cur[u]; e; e = next[e])
if (edge[e] && lev[u] < lev[v = ver[e]]) {
delta = dinic(v, std::min(edge[e], flow - res));
if (delta) {
edge[e] -= delta;
edge[e ^ 1] += delta;
res += delta;
if (res == flow)
break;
}
}
if (res != flow)
lev[u] = 0;
return res;
}
int main() {
scanf("%d", &n);
S = n + 1, E = n + 2;
int tmp, x;
for (int i = 1; i <= n; i++)
scanf("%d", &x), add(S, i, x);
for (int i = 1; i <= n; i++) {
tmp = 0;
for (int j = 1; j <= n; j++) {
scanf("%d", &x);
tmp += x;
if (x)
add(i, j, x << 1);
}
add(i, E, tmp);
ans += tmp;
}
while (dfs())
ans -= dinic(S, 1000000000);
printf("%d", ans);
}