【bzoj3996】[TJOI2015]线性代数

2015.05.01 15:01 Fri | 28次阅读 | 旧日oi | 固定链接 | 源码

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

2

HINT

 1<=N<=500

题解

真神题……画了好久也没明白咋回事,然后就请教了旁边的POPOQQQ大爷~
把B矩阵的每个元素看作选某个实验的利益,每个元素的行和列看作所需要的仪器,C矩阵看作每个仪器需要的代价,然后就是经典的最小割了

我的程序

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<vector>
#include<bitset>
#include<stack>
#include<ctime>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#define maxn 100010
#define ll long long
#define mod 1000000007
#define inf 0x3f3f3f3f
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;
}
int n,x,sum,S,T;
struct edge{
    int to,next,flow;
}e[505*505*10];
int h[505*505*2],tp;
void ae(int u,int v,int w)
{
    e[tp].to=v;
    e[tp].next=h[u];
    e[tp].flow=w;
    h[u]=tp++;
}
void add(int u,int v,int w)
{
    ae(u,v,w);ae(v,u,0);
}
int dis[505*505*2];
queue<int> q;
bool bfs()
{
    memset(dis,0,sizeof(dis));dis[S]=1;
    while(!q.empty()) q.pop();q.push(S);
    while(!q.empty())
    {
        int u=q.front();q.pop();
        for(int v,i=h[u];i!=-1;i=e[i].next)
        if(e[i].flow&&!dis[v=e[i].to])
        {
            dis[v]=dis[u]+1;
            if(v==T) return 1;
            q.push(v);
        }
    }
    return 0;
}
int dfs(int u,int limit)
{
    if(u==T) return limit;
    int tmp,cost=0;
    for(int v,i=h[u];i!=-1;i=e[i].next)
    if(e[i].flow&&dis[v=e[i].to]==dis[u]+1)
    {
        tmp=dfs(v,min(limit-cost,e[i].flow));
        if(tmp)
        {
            e[i].flow-=tmp;
            e[i^1].flow+=tmp;
            cost+=tmp;
            if(cost==limit) break;
        }
        else dis[v]=-1;
    }
    return cost;
}
int main()
{
    n=read();
    S=0;T=n*(n+1)+1;
    memset(h,-1,sizeof(h));
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            x=read();sum+=x;
            add(S,i*n+j,x);
            add(i*n+j,i,inf);
            add(i*n+j,j,inf);
        }
    }
    for(int i=1;i<=n;i++)
    {
        x=read();
        add(i,T,x);
    }
    while(bfs()) sum-=dfs(S,inf);
    cout<<sum<<endl;
}```