题面
题解
先化一波式子：
[D = (A cdot B - C)A^T
]
[= sum_{i = 1}^{n}H_{1i}cdot A^T_{i1}
]
[H_{1i} = (sum_{j = 1}^{n}A_{1j} cdot B_{ji}) - C_{1i}
]
[D = sum_{i = 1}^{n}{((sum_{j = 1}^{n}A_{1j} cdot B_{ji}) - C_{1i}) A^T_{i1}}
]
[D = sum_{i = 1}^{n}{((sum_{j = 1}^{n}A_{1j} cdot B_{ji}) - C_{1i}) A_{1i}}
]
[= sum_{i = 1}^{n} sum_{j = 1}^{n}A_j cdot B_{ji} cdot A_i - sum_{i = 1}^{n}C_iA_i
]
[= sum_{i = 1}^{n} sum_{j = 1}^{n}A_i cdot B_{ij} cdot A_j - sum_{i = 1}^{n}C_iA_i
]
因此选(i)和(j)则得到(B_{ij})的贡献，选(i)则花费(C_i)的代价。
因此我们有如下关系:选((i, j))则必选(i, j).
因此建图方式如下：
- 对于每个二元组((i, j)),我们连(s --- > (i, j) : B_{ij})
- 对于每个二元组((i, j)),我们连((i, j) ---> i : inf , (i, j) ---> j : inf)
- 对于每个点(i),我们连(i ---> t : C_i)
#include<bits/stdc++.h>
using namespace std;
#define R register int
#define AC 550
#define ac 1000000
#define maxn 3000000
#define inf 1000000000
//#define D printf("in line %d
", __LINE__);
int n, s, t, x, addflow, ans, all;
int B[AC][AC], C[AC];
int Head[ac], date[maxn], Next[maxn], haveflow[maxn], tot = 1;
int have[ac], good[ac], c[ac], last[ac];
int q[ac], head, tail;
inline int read()
{
int x = 0;char c = getchar();
while(c > '9' || c < '0') c = getchar();
while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
return x;
}
inline void upmin(int &a, int b) {if(b < a) a = b;}
inline void upmax(int &a, int b) {if(b > a) a = b;}
inline void add(int f, int w, int S)
{
date[++ tot] = w, Next[tot] = Head[f], Head[f] = tot, haveflow[tot] = S;
date[++ tot] = f, Next[tot] = Head[w], Head[w] = tot, haveflow[tot] = 0;
//printf("%d --- > %d : %d
", f, w, S);
}
void bfs()
{
q[++ tail] = t, have[1] = c[t] = 1;
while(head < tail)
{
int x = q[++ head];
for(R i = Head[x]; i; i = Next[i])
{
int now = date[i];
if(!c[now] && haveflow[i ^ 1])
{
++ have[c[now] = c[x] + 1];
q[++ tail] = now;
}
}
}
memcpy(good, Head, sizeof(good));
}
void aru()
{
while(x != s)
{
haveflow[last[x]] -= addflow;
haveflow[last[x] ^ 1] += addflow;
x = date[last[x] ^ 1];
}
ans -= addflow, addflow = inf;
}
void ISAP()
{
bool done = false;
addflow = inf, x = s;
while(c[t] != all + 10)
{
if(x == t) aru();
done = false;
for(R i = good[x]; i; i = Next[i])
{
int now = date[i];
good[x] = i;
if(c[now] == c[x] - 1 && haveflow[i])
{
upmin(addflow, haveflow[i]);
last[now] = i, x = now, done = true;
break;
}
}
if(!done)
{
int go = all + 9;
for(R i = Head[x]; i; i = Next[i])
if(c[date[i]] && haveflow[i]) upmin(go, c[date[i]]);
good[x] = Head[x];
if(!(-- have[c[x]])) break;
have[c[x] = go + 1] ++;
if(x != s) x = date[last[x] ^ 1];
}
}
printf("%d
", ans);
}
void pre()
{
n = read(), all = n * n + n, s = all + 1, t = s + 1;
for(R i = 1; i <= n; i ++)
for(R j = 1; j <= n; j ++) B[i][j] = read(), ans += B[i][j];
for(R i = 1; i <= n; i ++) C[i] = read();
}
inline int id(int i, int j){return (i - 1) * n + j;}
void build()
{
for(R i = 1; i <= n; i ++)
for(R j = 1; j <= n; j ++)
{
int ID = id(i, j);
add(s, ID, B[i][j]);
add(ID, n * n + i, inf), add(ID, n * n + j, inf);
}
for(R i = 1; i <= n; i ++) add(n * n + i, t, C[i]);
}
int main()
{
// freopen("in.in", "r", stdin);
pre();
build();
bfs();
ISAP();
// fclose(stdin);
return 0;
}