http://www.lydsy.com/JudgeOnline/problem.php?id=2039
题意：中文题意。
思路：一开始想着和之前做的最大权闭合图有点像，但是如果把边全部当成点的话，那么点也太多了。
对于这种选和不选的方案问题，还是一样用最小割来解决，求最小的损失收益，然后用能够得到的总收益去减去最小割的值就是答案。思维模式是：将S集或者T集的某一边当成是选择的，另一边当成是不选择的，根据这样去连边，就可能更容易想到建图方案。
在这题里面，我把T集当成是选择的人，把S集当成是不选择的人。这样的话如果选择一个人，那么就损失了雇佣他的钱，于是将A[i]和S相连，代表如果不割这条边的话，那么它就会划入S集。同理如果不雇佣一个人，损失的E[i]和T相连，代表如果不割这条边的话，那么它就划入T集，代表选择这个人。有了上面这两个主要的建边，接下来就很容易想到将人与人之间连一条容量为互相的贡献E[i,j]*2（题意）的无向边，代表如果选了i，那么可以对j作出E[i,j]的贡献，选j同理。
这样图的点数其实就是人数+2而已。记得要开longlong，还有损失的E[i]要先合并起来，否则边过多。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
#define N 1010
#define INF 0x3f3f3f3f
typedef long long LL;
struct Edge {
int u, v; LL cap; int nxt;
} edge[N*N*];
int cur[N], gap[N], dis[N], pre[N], tot, head[N], S, T;
LL mp[N][N], e[N]; void Add(int u, int v, LL cap) {
edge[tot] = (Edge) {u, v, cap, head[u]}; head[u] = tot++;
edge[tot] = (Edge) {v, u, , head[v]}; head[v] = tot++;
} int BFS() {
queue<int> que;
que.push(T);
memset(dis, INF, sizeof(dis));
memset(gap, , sizeof(gap));
dis[T] = ; gap[]++;
while(!que.empty()) {
int u = que.front(); que.pop();
for(int i = head[u]; ~i; i = edge[i].nxt) {
if(dis[edge[i].v] == INF) {
dis[edge[i].v] = dis[u] + ;
gap[dis[edge[i].v]]++;
que.push(edge[i].v);
}
}
}
} LL ISAP(int n) {
BFS();
memcpy(cur, head, sizeof(cur));
LL ans = , flow;
int i, u = pre[S] = S, index;
while(dis[S] < n) {
if(u == T) {
flow = ;
for(i = S; i != T; i = edge[cur[i]].v)
if(flow > edge[cur[i]].cap) flow = edge[cur[i]].cap, index = i;
for(i = S; i != T; i = edge[cur[i]].v)
edge[cur[i]].cap -= flow, edge[cur[i]^].cap += flow;
ans += flow; u = index;
}
for(i = cur[u]; ~i; i = edge[i].nxt) if(dis[edge[i].v] == dis[u] - && edge[i].cap) break;
if(~i) { cur[u] = i; pre[edge[i].v] = u; u = edge[i].v; }
else {
int md = n + ;
if(--gap[dis[u]] == ) break;
for(i = head[u]; ~i; i = edge[i].nxt)
if(md > dis[edge[i].v] && edge[i].cap) md = dis[edge[i].v], cur[u] = i;
gap[dis[u] = md + ]++;
u = pre[u];
}
}
return ans;
} int main() {
int n; LL w, sum = ;
scanf("%d", &n);
S = ; T = n + ;
memset(head, -, sizeof(head)); tot = ;
for(int i = ; i <= n; i++)
scanf("%lld", &w), Add(S, i, w);
for(int i = ; i <= n; i++) for(int j = ; j <= n; j++) scanf("%lld", &mp[i][j]), e[i] += mp[i][j], sum += mp[i][j];
for(int i = ; i <= n; i++) {
Add(i, T, e[i]);
for(int j = i + ; j <= n; j++) {
Add(i, j, mp[i][j] * ); Add(j, i, mp[i][j] * );
}
}
LL ans = ISAP(T + );
printf("%lld\n", sum - ans);
return ;
}