【题意】：给出一个矩阵方程D = (A * B - C) * A
T，已知矩阵B[n*n]和矩阵C[1*n]，现在要你求一个01矩阵A[1*n]使得D最大，问D最大是多少。
【题解】：这个题目可以转化为poj 3469.
对于矩阵B来说，选到某一列i，那么也要选到C[i]。于是可以转化一下问题，对于B的每一列都存在选与不选的情况，而这些情况刚刚好对应着矩阵A。
那么我们假设先把B的所有列都选上，再通过调整。如果B某一列i不选，那么代价是这一列的和，如果选上，代价就是C[i]，对于选择了列i而没选列j这种情况，我们的代价是B[i][j]，于是我们可以把问题转化为最小割。
把每列抽象成一个结点。
源点s连边每列，容量为这一列的和；
每一列向汇点t连边，容量为C[i]；
列i向列j连边，容量为b[j][i]；
最后答案就是 ∑b[i][j] - mincut / maxflow.
【代码】：
1 #include "iostream"
2 #include "cstdio"
3 #include "cstring"
4 #include "algorithm"
5 #include "vector"
6 #include "queue"
7 #include "cmath"
8 #include "string"
9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 #include "set"
13 #include "utility"
14 using namespace std;
15 typedef pair<int, int> pii;
16 #define pb push_back
17 #define mp make_pair
18 #define fi first
19 #define se second
20 #define sof(x) sizeof(x)
21 #define lc(x) (x << 1)
22 #define rc(x) (x << 1 | 1)
23 #define lowbit(x) (x & (-x))
24 #define ll long long
25 #define maxn 1050
26 #define maxm 3000000
27 const int inf = 1 << 30;
28 int n, m, s, t;
29 int b[maxn][maxn], c[maxn], cc[maxn];
30 int eh[maxn], low[maxn], dist[maxn], pre[maxn], cur[maxn], tot, cnt[maxn];
31 struct Edge {
32 int u, v, cap, flow, next;
33 }et[maxm];
34 void init() {
35 tot = 0;
36 memset(eh, -1, sizeof(eh));
37 }
38 void add(int u, int v, int cap, int flow) {
39 Edge e = {u, v, cap, flow, eh[u]};
40 et[tot] = e;
41 eh[u] = tot++;
42 }
43 void addedge(int u, int v, int cap) {
44 add(u, v, cap, 0), add(v, u, 0, 0);
45 }
46 int isap(int s, int t, int n){
47 int u, v, now, flow = 0;
48 memset(dist, 0, sizeof(dist));
49 memset(low, 0, sizeof(low));
50 memset(cnt, 0, sizeof(cnt));
51 for(u = 0 ; u <= n ; u ++) cur[u] = eh[u];
52 low[s] = inf, cnt[0] = n, u = s;
53 while(dist[s] < n) {
54 for(now = cur[u]; now != -1; now = et[now].next)
55 if(et[now].cap - et[now].flow && dist[u] == dist[ v = et[now].v ] + 1 ) break;
56 if(now != -1) {
57 cur[u] = pre[v] = now;
58 low[v] = min(et[now].cap - et[now].flow, low[u]);
59 u = v;
60 if(u == t) {
61 for(; u != s; u = et[pre[u]].u){
62 et[pre[u]].flow += low[t];
63 et[pre[u]^1].flow -= low[t];
64 }
65 flow += low[t]; low[s] = inf;
66 }
67 } else {
68 if(--cnt[dist[u]] == 0) break;
69 dist[u] = n, cur[u] = eh[u];
70 for(now = eh[u]; now != -1; now = et[now].next)
71 if(et[now].cap - et[now].flow && dist[u] > dist[et[now].v] + 1)
72 dist[u] = dist[ et[now].v ] + 1;
73 cnt[dist[u]]++;
74 if(u != s) u = et[pre[u]].u;
75 }
76 }
77 return flow;
78 }
79
80 void build() {
81 s = 0, t = n + 1;
82 for(int i = 1; i <= n; i++) addedge(s, i, cc[i]), addedge(i, t, c[i]);
83 for(int i = 1; i <= n; i++)
84 for(int j = 1; j <= n; j++)
85 if(i != j) addedge(j, i, b[i][j]);
86 }
87
88 int main() {
89 int T;
90 scanf("%d", &T);
91 while(T--) {
92 init();
93 scanf("%d", &n);
94 int sum = 0;
95 memset(cc, 0, sizeof(cc));
96 for(int i = 1; i <= n; i++)
97 for(int j = 1; j <= n; j++) {
98 scanf("%d", &b[i][j]);
99 sum += b[i][j];
100 cc[j] += b[i][j];
101 }
102 for(int i = 1; i <= n; i++) scanf("%d", &c[i]);
103 build();
104 int cut = isap(s, t, n + 2);
105 printf("%d\n", sum - cut);
106
107 }
108 return 0;
109 }
110