BZOJ3996: [TJOI2015]线性代数 解题报告

Description

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

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

---

---

---

题解

可以化简一下公式

(A∗B−C)∗AT=A∗B∗AT−C∗AT=∑ai∗aj∗bi,j−∑ai∗ci

所以问题可以化为一些物品，选物品 i 需要花费 ci ，如果同时选了 i,j 两个物品，可以获得 bi,j 的价值，问价值减花费最大值是多少
然后这是一个经典的最小割的模型………

---

code：

#include<set>
#include<map>
#include<deque>
#include<queue>
#include<stack>
#include<cmath>
#include<ctime>
#include<vector>
#include<string>
#include<bitset>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<climits>
#include<complex>
#include<iostream>
#include<algorithm>
#define ll long long
#define inf 1e9
using namespace std;

const int maxn = 510;
queue<int>Q;
struct edge
{
int y,c,next;
}a[maxn*maxn<<1]; int len,first[maxn];
int h[maxn];
int st,ed;
void insert(int x,int y,int c)
{
    len++;
    a[len].y=y;a[len].c=c;a[len].next=first[x];first[x]=len;
    len++;
    a[len].y=x;a[len].c=0;a[len].next=first[y];first[y]=len;
}
bool bfs()
{
memset(h,0,sizeof h);
    Q.push(st); h[st]=1;
while(!Q.empty())
    {
int x=Q.front(); Q.pop();
for(int k=first[x];k;k=a[k].next)
        {
int y=a[k].y;
if(h[y]==0&&a[k].c)
            {
                h[y]=h[x]+1;
                Q.push(y);
            }
        }
    }
return h[ed]>0;
}
int dfs(int x,int flow)
{
if(x==ed)return flow;
int delta=0;
for(int k=first[x];k;k=a[k].next)
    {
int y=a[k].y;
if(h[y]==h[x]+1&&a[k].c&&delta<flow)
        {
int minx=dfs(y,min(flow-delta,a[k].c));
            a[k].c-=minx; a[k^1].c+=minx;
            delta+=minx;
        }
    }
if(delta==0)h[x]=0;
return delta;
}

int b[maxn][maxn],c[maxn];
int n,ret;

int main()
{
    len=1;memset(first,0,sizeof first);

scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++) scanf("%d",&b[i][j]),ret+=b[i][j];
for(int i=1;i<=n;i++) scanf("%d",&c[i]);

    st=n+1; ed=n+2;
for(int i=1;i<=n;i++)
    {
int k=0;
for(int j=1;j<i;j++)
                insert(j,i,b[i][j]+b[j][i]),k+=b[i][j]+b[j][i];
        insert(st,i,c[i]);insert(i,ed,k+b[i][i]);
    }
//printf("%d\n",ret);
while(bfs()) 
        ret-=dfs(st,inf);
printf("%d\n",ret);

return 0;
}