【BZOJ-3996】线性代数最小割-最大流

3996: [TJOI2015]线性代数

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1054 Solved: 684
[Submit][Status][Discuss]

Description

给出一个N*N的矩阵B和一个1*N的矩阵C。求出一个1*N的01矩阵A.使得

D=（A*B-C）*A^T最大。其中A^T为A的转置。输出D

Input

第一行输入一个整数N，接下来N行输入B矩阵，第i行第J个数字代表Bij.

接下来一行输入N个整数，代表矩阵C。矩阵B和矩阵C中每个数字都是不超过1000的非负整数。

Output

输出最大的D

Sample Input

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

Sample Output

HINT

1<=N<=500

Source

Solution

首先来化简一下题目中的式子：

设$E=A*B$，很显然E为一个1×N的矩阵，那么有$E_{1,j}=sum_{i=1}^{N}A_{1,i}B_{i,j}$

那么$A*B-C$就可以化成$F_{1,j}=sum_{i=1}^{N}A_{1,i}B_{i,j}-C_{1,j}$

那么进一步化简$D_{1,1}=sum_{j=1}^{N}left ( left ( sum_{i=1}^{N}A_{1,i}B_{i,j}-C_{1,j} ight )*A'_{j,1} ight )$

最后化成：$D=sum_{i=1}^{N}sum_{j=1}^{N}A_{i}A_{j}B_{i,j}-sum_{i=1}^{N}A_{i}C_{i}$

那么从式子的角度去思考建图由于$A$是一个0/1矩阵，不妨把$A$看做“选”或“不选”，那么$B_{i,j}$看做同时选$i$和$j$两个物品的收益，$C_{i}$可以看做选第$i$个物品的代价。

也就是说选$B_{i,j}$必须选$C_{i},C_{j}$

最大权闭合子图.....

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
int read()
{
    int x=0,f=1; char ch=getchar();
    while (ch<'0' || ch>'9') {if (ch=='-')f=-1; ch=getchar();}
    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
#define maxn 300010
#define maxm 3000010
int N,tot,ans;
struct Edgenode{int to,next,cap;}edge[maxm];
int head[maxn],cnt=1;
void add(int u,int v,int w)
{cnt++;edge[cnt].to=v;edge[cnt].cap=w;edge[cnt].next=head[u];head[u]=cnt;}
void insert(int u,int v,int w)
{add(u,v,w);add(v,u,0);}
//
#define inf 0x7fffffff
int dis[maxn],q[maxn<<1],cur[maxn],S,T;
bool bfs()
{
    for (int i=S; i<=T; i++) dis[i]=-1;
    q[0]=S; int he=0,ta=1;
    while (he<ta)
        {
            int now=q[he++];
            for (int i=head[now]; i; i=edge[i].next)
                if (edge[i].cap && dis[edge[i].to]==-1)
                    dis[edge[i].to]=dis[now]+1,q[ta++]=edge[i].to;
        }
    return dis[T]!=-1;
}
int dfs(int loc,int low)
{
    if (loc==T) return low;
    int w,used=0;
    for (int i=cur[loc]; i; i=edge[i].next)
        if (edge[i].cap && dis[edge[i].to]==dis[loc]+1)
            {
                w=dfs(edge[i].to,min(low-used,edge[i].cap));
                edge[i].cap-=w; edge[i^1].cap+=w;
                used+=w; if (edge[i].cap) cur[loc]=i;
                if (used==low) return low;
            }
    if (!used) dis[loc]=-1;
    return used;
}
int dinic()
{
    int tmp=0;
    while (bfs())
        {
            for (int i=S; i<=T; i++) cur[i]=head[i];
            tmp+=dfs(S,inf);
        }
    return tmp;
}
//
int main()
{
    N=read(); S=0,T=N+N*N+1;
    for (int i=1; i<=N; i++)
        for (int x,j=1; j<=N; j++)
            x=read(),tot+=x,insert((i-1)*N+j+N,T,x),
            insert(i,(i-1)*N+j+N,inf),insert(j,(i-1)*N+j+N,inf);
    for (int x,i=1; i<=N; i++)
        x=read(),insert(S,i,x);
    ans=dinic();
    printf("%d
",tot-ans);
    return 0;
}

正解被喝水路过的ShallWe直接秒....不然我还没往最小割模型上靠...