展开
(D=(AB-C)A^T\ =sum_{i=1}^n(sum_{j=1}^na_jb_{j,i}-c_i)a_i\ =sum_{i=1}^nsum_{j=1}^na_ia_jb_{i,j}-sum_{i=1}^na_ic_i)
对每一对 (i,j),同时选获得 (b_{ij}+b_{ji})
某个 (i) 不选,额外损失 (c_i)
考虑最大权闭合子图
(S o (i,j)= b_{ij}+b_{ji})
((i,j) o i (j) = infty)
(i o T= c_i)
跑最大流即可,最后用 (sum b_{ij}) 减去答案
#include <bits/stdc++.h>
using namespace std;
const int inf = 1e+9;
namespace flow {
const int maxn = 300005;
const int inf = 1e+9;
int dis[maxn], ans, cnt = 1, s, t, pre[maxn * 10], nxt[maxn * 10], h[maxn], v[maxn * 10];
std::queue<int> q;
void make(int x, int y, int z) {
pre[++cnt] = y, nxt[cnt] = h[x], h[x] = cnt, v[cnt] = z;
pre[++cnt] = x, nxt[cnt] = h[y], h[y] = cnt;
}
bool bfs() {
memset(dis, 0, sizeof dis);
q.push(s), dis[s] = 1;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int i = h[x]; i; i = nxt[i])
if (!dis[pre[i]] && v[i])
dis[pre[i]] = dis[x] + 1, q.push(pre[i]);
}
return dis[t];
}
int dfs(int x, int flow) {
if (x == t || !flow)
return flow;
int f = flow;
for (int i = h[x]; i; i = nxt[i])
if (v[i] && dis[pre[i]] > dis[x]) {
int y = dfs(pre[i], min(v[i], f));
f -= y, v[i] -= y, v[i ^ 1] += y;
if (!f)
return flow;
}
if (f == flow)
dis[x] = -1;
return flow - f;
}
int solve(int _s,int _t) {
s=_s;
t=_t;
ans = 0;
for (; bfs(); ans += dfs(s, inf));
return ans;
}
}
int n,b[505][505],c[505];
int id_node(int p) {
return 2+p;
}
int id_pair(int p,int q) {
return 2+p*n+q;
}
int main() {
scanf("%d",&n);
int sum = 0;
for(int i=1;i<=n;i++) {
for(int j=1;j<=n;j++) {
scanf("%d",&b[i][j]);
sum += b[i][j];
flow::make(1,id_pair(i,j),b[i][j]);
flow::make(id_pair(i,j),id_node(i),inf);
flow::make(id_pair(i,j),id_node(j),inf);
}
}
for(int i=1;i<=n;i++) {
scanf("%d",&c[i]);
flow::make(id_node(i),2,c[i]);
}
cout<<sum - flow::solve(1,2);
}