题解：P1791 [国家集训队] 人员雇佣
Pengzt
·
·
题解
Problem
给定 N 个元素 a_i，你需要把它们分成两个集合 A, B。对于一个划分方案，代价为：
\left(\sum_{i \in A} a_i\right) + \sum_{i\in A}\left(\sum_{j\in A} E_{i, j} - \sum_{j\in B} E_{i, j}\right)
求划分的最小代价。
### Sol
这种二选一的东西，不难想到最小割。令 $s_i = \sum_{j} E_{i, j}$。
对于 $i \in [1, n]$，连边 $(S, i, s_i)$，$(i, T, A_i)$。
对于 $i \in [1, n], j \in [1, n]$，连边 $(i, j, 2E_{i, j})$。
求最小割即可。
### Code
远古代码，看看就好。
```cpp
#include<bits/stdc++.h>
#define ll long long
#define sz(a) ((int) (a).size())
#define vi vector < int >
#define pb emplace_back
using namespace std;
int n;
int a[1010];
struct Flow {
const ll inf = 1e18;
int n, S, T;
struct node {
int v; ll w; int b;
node(int _v, ll _w, int _b) {
v = _v, w = _w, b = _b;
}
};
vector < vector < node > > e;
vi dis, cur, q;
Flow(int _n) : e(_n + 10), dis(_n + 10), cur(_n + 10), q(_n + 10) {
n = _n;
}
void adde(int u, int v, ll w) {
e[u].pb(v, w, sz(e[v]));
e[v].pb(u, 0, sz(e[u]) - 1);
}
int hd, tl;
bool bfs() {
for(int i = 0; i <= n; ++i) dis[i] = cur[i] = 0;
q[hd = tl = 1] = S;
dis[S] = 1;
while(hd <= tl) {
int u = q[hd++];
for(auto i : e[u]) {
int v = i.v;
if(i.w && !dis[v]) {
dis[v] = dis[u] + 1;
q[++tl] = v;
if(i.v == T) return 1;
}
}
}
return 0;
}
ll dfs(int u, ll flow) {
if(u == T) return flow;
ll res = 0;
for(int &i = cur[u]; i < sz(e[u]); ++i) {
int v = e[u][i].v;
if(e[u][i].w && dis[v] == dis[u] + 1) {
ll fl = dfs(v, min(flow, e[u][i].w));
e[u][i].w -= fl, e[v][e[u][i].b].w += fl;
flow -= fl, res += fl;
if(!flow) return res;
}
}
return res;
}
ll maxflow(int _S, int _T) {
S = _S, T = _T;
ll res = 0;
while(bfs()) res += dfs(S, inf);
return res;
}
};
int main() {
ios :: sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cin >> n;
int S = n + 1, T = n + 2;
Flow G(T);
for(int i = 1; i <= n; ++i)
cin >> a[i],
G.adde(i, T, a[i]);
ll sum = 0;
for(int i = 1; i <= n; ++i) {
ll s = 0;
for(int j = 1, x; j <= n; ++j) {
cin >> x;
s += x;
G.adde(i, j, 2 * x);
}
G.adde(S, i, s);
sum += s;
}
cout << sum - G.maxflow(S, T) << "\n";
return 0;
}
```