BZOJ3996 线性代数

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=3996

转化题目给的条件

$$D = \sum_{i=1}^n \sum_{j=1}^n{A(i)A(j)B(i,j)} - \sum_{i=1}^n C(i)A(i)$$

网络流可解，如果要得到 $B(i,j)$ 的话必须选$i$物品和$j$物品然后，选择每一个物品都有其代价。

最大权闭合子图。

再流网络中割掉一条边就是舍弃一个$B(i,j)$

所以最小割即可。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <queue>

#define N 1100010

#define INF 0x3f3f3f3f

using namespace std;

struct edge{

    int x,to,cap;

}E[N<<];

int n,B[][],C[N],totE,g[N],S,T,h[N],tot;

queue<int> q;

bool v[N];

#define p E[i].x

void ade(int x,int y,int cap){

    E[++totE]=(edge){y,g[x],cap}; g[x]=totE;

    E[++totE]=(edge){x,g[y],};   g[y]=totE;

}

bool bfs(){

    memset(v,,sizeof(v));

    q.push(S); h[S]=; v[S]=;

    while(!q.empty()){

        int x=q.front(); q.pop();

        for(int i=g[x];i;i=E[i].to)

            if(E[i].cap&&!v[p]){

                h[p]=h[x]+;

                q.push(p); v[p]=;

            }

    }

    return v[T];

}

int dinic(int x,int flow){

    if(x==T||!flow) return flow;

    int f=;

    for(int i=g[x];i&&flow;i=E[i].to)

        if(h[p]==h[x]+&&E[i].cap){

            int tmp=dinic(p,min(flow,E[i].cap));

            E[i].cap-=tmp; E[i^].cap+=tmp;

            f+=tmp; flow-=tmp;

        }

    if(!f) h[x]=-;

    return f;

}

int main(){

    scanf("%d",&n);

    for(int i=,j;i<=n;i++)

        for(j=;j<=n;j++) scanf("%d",&B[i][j]);

    for(int i=;i<=n;i++) scanf("%d",&C[i]);

    S=n*n+n+; T=S+;

    for(int i=;i<=n;i++) ade(i,T,C[i]);

    int ans=;

    tot=n;

    for(int i=;i<=n;i++)

        for(int j=;j<=n;j++){

            ans+=B[i][j];

            ade(S,++tot,B[i][j]);

            ade(tot,j,INF);

            ade(tot,i,INF);

        }

    while(bfs()) ans-=dinic(S,INF);

    printf("%d\n",ans);

    return ;

}

看来真的需要补线性代数呀。