BZOJ3996【TJOI2015】线性代数 <最大权闭合子图>

Problem

【TJOI2015】线性代数

$\mathrm{Time\;Limit:\;10\;Sec}$
$\mathrm{Memory\;Limit:\;128\;MB}$

Description

给出一个$N\times N$的矩阵$B$和一个$1\times N$的矩阵$C$。
求出一个$1\times N$的$01$矩阵$A$，使得$D=(A\times B-C)\times A^T$最大，输出最大的$D$值。

Input

第一行输入一个整数$N$。
接下来$N$行输入$B$矩阵，第$i$行第$j$个数字代表$B_{i,j}$.
接下来一行输入$N$个整数，代表矩阵$C$。
矩阵$B$和矩阵$C$中每个数字都是不超过$1000$的非负整数。

Output

输出最大的$D$。

Sample Input

3
1 2 1
3 1 0
1 2 3
2 3 7

Sample Output

2

Hint

$1\le N\le500$

标签：网络流 最大权闭合子图

Solution

先化简一下$D$，用和式表示：

$$\begin{aligned} D &= \begin {pmatrix} A_1\;A_2\;\cdots\;A_n \end {pmatrix} \times \begin {pmatrix} B_{1,1}&B_{1,2}&\cdots&B_{1,n}\\ B_{2,1}&B_{2,2}&\cdots&B_{2,n}\\ \vdots&\vdots&\ddots&\vdots\\ B_{n,1}&B_{n,2}&\cdots&B_{n,n} \end {pmatrix} \times \begin {pmatrix} A_1\\A_2\\\vdots\\A_n \end {pmatrix} - \begin {pmatrix} C_1\;C_2\;\cdots\;C_n \end {pmatrix} \times \begin {pmatrix} A_1\\A_2\\\vdots\\A_n \end {pmatrix} \\ &= \begin {pmatrix} \sum_{i=1}^{n}A_iB_{i,1}&\sum_{i=1}^{n}A_iB_{i,2}&\cdots&\sum_{i=1}^{n}A_iB_{i,n} \end {pmatrix} \times \begin {pmatrix} A_1\\A_2\\\vdots\\A_n \end {pmatrix} - \begin {pmatrix} C_1\;C_2\;\cdots\;C_n \end {pmatrix} \times \begin {pmatrix} A_1\\A_2\\\vdots\\A_n \end {pmatrix} \\ &= \sum_{i=1}^{n}\sum_{j=1}^{n}A_iA_jB_{i,j}-\sum_{i=1}^{n}A_iC_i \end{aligned}$$

由于$A$是$01$矩阵，可以将其看作有$n$个物品，选择取或不去，第$i$给物品取有$C_i$的代价，第$i$个和第$j$个同时取会有$B_{i,j}$的贡献。要求使总贡献$D$最大。

对于每个物体建一个点，任意两个物体的组合建一个点。对于组合$<i,j>$，连接其代表的点和第$i$个物体的点与第$j$个物体的点。对于物体的点，权值设为$-C_i$，对于组合的点，权值设为$B_{i,j}$。这样选择一个组合的点，必须将其连向的两个物体的点也选择，即变为最大权闭合子图模型。

建模：

• 对每个物体$i$建一个点$p_i$，连接$p_i\to T$流量$C_i$
• 对每个组合$<i,j>$建一个点$p_{i,j}$，连接$S\to p_{i,j}$流量$B_{i,j}$
• 对于每个组合$<i,j>$，连边$p_{i,j}\to p_i$流量$\infty$，连边$p_{i,j}\to p_j$流量$\infty$

跑最大流求最小割，答案为$\sum_{i=1}^{n}\sum_{j=1}^{n}B_{i,j}-最小割$。

Code

#include <bits/stdc++.h>
#define MAX_N 300000
#define MAX_M 2000000
#define INF 0x3f3f3f3f
using namespace std;
template <class T> inline void read(T &x) {
    x = 0; int c = getchar(), f = 1;
    for (; !isdigit(c); c = getchar()) if (c == 45) f = -1;
    for (; isdigit(c); c = getchar()) (x *= 10) += f*(c-'0');
}
int n, s, t, cnt, tot;
int d[MAX_N+5], pr[MAX_N+5], cr[MAX_N+5];
struct node {int v, c, nxt;} E[MAX_M+5];
void init() {s = 0, t = n*n+n+1, cnt = 0, memset(pr, -1, sizeof pr);}
void insert(int u, int v, int c) {E[cnt] = (node){v, c, pr[u]}, pr[u] = cnt++;}
void addedge(int u, int v, int c) {insert(u, v, c), insert(v, u, 0);}
bool BFS() {
    queue <int> que; que.push(s);
    memset(d, -1, sizeof d), d[s] = 0;
    while (!que.empty()) {
        int u = que.front(); que.pop();
        for (int i = pr[u]; ~i; i = E[i].nxt) {
            int v = E[i].v, c = E[i].c;
            if (~d[v] || !c) continue;
            d[v] = d[u]+1, que.push(v);
        }
    }
    return ~d[t];
}
int DFS(int u, int flow) {
    if (u == t) return flow; int ret = 0;
    for (int &i = pr[u]; ~i; i = E[i].nxt) {
        int v = E[i].v, c = E[i].c;
        if (d[u]+1 != d[v] || !c) continue;
        int tmp = DFS(v, min(flow, c));
        E[i].c -= tmp, E[i^1].c += tmp;
        flow -= tmp, ret += tmp;
        if (!flow) break;
    }
    if (!ret) d[u] = -1;	return ret;
}
void cpy() {for (int i = s; i <= t; i++) cr[i] = pr[i];}
void rec() {for (int i = s; i <= t; i++) pr[i] = cr[i];}
int Dinic() {int ret = 0; cpy(); while (BFS()) ret += DFS(s, INF), rec(); return ret;}
int main() {
    read(n), init();
    for (int i = 1; i <= n; i++)
        for (int j = 1, b; j <= n; j++)
            read(b), tot += b, addedge(s, (i-1)*n+j, b);
    for (int i = 1, c; i <= n; i++)
        read(c), addedge(n*n+i, t, c);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            addedge((i-1)*n+j, n*n+i, INF), 
            addedge((i-1)*n+j, n*n+j, INF);
    return printf("%d\n", tot-Dinic()), 0;
}