P1791 [国家集训队]人员雇佣

· · 题解

这是一篇拥有比较详细的证明的题解。

人员雇佣

给出 n 个人，每个人的雇佣费用为 a_i，两个人之间有价值度 E(i,j)。

要求选择一些人，假设选择的集合为 A，那么总利益就是 \sum_{i,j\in A} E(i,j)-\sum_{i\in A,j\not\in A} E(i,j)-\sum_{i\in A} a_i。

求总利益的最大值。

首先通过补集思想转化一下：

\sum_{i\in A,j\not\in A} E(i,j)=\sum_{i\in A} C_i-\sum_{i\in A,j\in A} E(i,j)

其中 C_i 表示从点 i 连出的所有边，这显然是正确的。所以有：

W=2\sum_{i\in A,j\in A} E(i,j)-\sum_{i\in A} a_i+C_i

题目要求是最大化 W，而对于点 i，a_i,C_i 一定是定值，可以预处理出来。

这样就是一个比较标准的最小割模型了，容易想到：

  1. 连边 (S,i,C_i)。
  2. 连边 (T,i,a_i)。
  3. 对于 E(i,j)，连边 (i,j,2\times E(i,j))。

然后用 \sum_{i=1}^n \sum_{j=1}^n E(i,j) 减去最小割即可，下面尝试证明一下这样建模的正确性。（理性愉悦）

首先是假设将所有雇员全部雇佣，然后要么减去贡献，要么减去雇佣费用。

相同的，在最小割中，要么直接割掉 (S,i,C_i) 的边，表示直接不选 i，即减去贡献、

要么直接割掉 (i,T,a_i)，表示雇佣 i，即减去雇佣费用。

但是对于第二种的情况，它还是有可能使原图连通（存在连边 3）。

所以还需要割掉所有 (i,j,2\times E(i,j))，其中 j 是所有没有割掉 (j,T,a_j) 的边。（否则这样就可以通过 S\to i\to j\to T 连通）

这恰好对应了，如果选择 i 而没有选择 j 就需要减去 E(i,j) 这一条件，也就是只统计 2\sum_{i\in A,j\in A} E(i,j)。

另外，这道题没必要使用 long long，但之前为了保险还是开了，导致直接 T 到 50pts，深刻体会到 long long 的效率问题。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;

const int INF = 1 << 30;
const int N = 1010;
const int M = N * N * 2;

int n, a[N], c[N], w[N][N];
int S, T, cnt = 1, head[N], now[N], d[N];
struct Edge{int nxt, to, val;} ed[M];
queue<int> q;

int read() {
    int x = 0, f = 1; char c = getchar();
    while (c < '0' || c > '9') f = (c == '-') ? -1 : 1, c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - 48, c = getchar();
    return x * f;
}

void add(int u, int v, int w){
    ed[++ cnt] = (Edge){head[u], v, w}; head[u] = cnt;
    ed[++ cnt] = (Edge){head[v], u, 0}; head[v] = cnt;
}

bool bfs(){
    while(!q.empty()) q.pop();
    memset(d, 0, sizeof(d));
    d[S] = 1, now[S] = head[S]; q.push(S);
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int i = head[u]; i; i = ed[i].nxt){
            int v = ed[i].to, w = ed[i].val;
            if(w && !d[v]){
                d[v] = d[u] + 1;
                now[v] = head[v];
                if(v == T) return true;
                q.push(v);
            }
        }
    }
    return false;
}

int Dinic(int u, int flow){
    if(u == T) return flow;
    int rest = flow; int i;
    for(i = now[u]; i && rest; i = ed[i].nxt){
        int v = ed[i].to, w = ed[i].val;
        if(d[v] == d[u] + 1 && w){
            int k = Dinic(v, min(rest, w));
            if(!k) d[v] = 0;
            ed[i].val -= k;
            ed[i ^ 1].val += k;
            rest -= k;
        }
    }
    now[u] = i;
    return flow - rest;
}

int Max_Flow(){
    int Flow = 0, flow; 
    while(bfs())
        while(flow = Dinic(S, INF)) Flow += flow;
    return Flow;
}

int main(){
    n = read();
    for(int i = 1; i <= n; i ++) a[i] = read();
    int ans = 0;
    for(int i = 1; i <= n; i ++)
        for(int j = 1; j <= n; j ++){
            w[i][j] = read();
            if(i == j || !w[i][j]) continue;
            c[i] += w[i][j]; ans += w[i][j];
            add(i, j, 2 * w[i][j]);
        }
    S = n + 1, T = S + 1;
    for(int i = 1; i <= n; i ++)
        add(S, i, c[i]), add(i, T, a[i]);
    printf("%d\n", ans - Max_Flow());
    return 0;
}