【题意】:给出一个矩阵方程D = (A * B - C) * AT,已知矩阵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<intint> 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