[BZOJ3996][TJOI2015]线性代数 最大权闭合子图



画柿子,发现其实就是在求

的最大值.
这等于选每个物品需要Ci的花费,同时选i和j能够获得Bij的收益,求收益-花费最大值,就是个最大权闭合子图模型.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 252333
#define M 2333333
using namespace std;
const int inf=0x3bbbbbbb;
int n,s,t,ans,head[N],to[M],nxt[M],f[M],tot=1;
inline void add(int x,int y,int z)
{
    to[++tot]=y;nxt[tot]=head[x];head[x]=tot;f[tot]=z;
    to[++tot]=x;nxt[tot]=head[y];head[y]=tot;f[tot]=0;
}
int dis[N],q[N],l,r;
int bfs()
{
    l=1,r=0;
    memset(dis,-1,sizeof dis);
    q[++r]=s,dis[s]=0;
    int x,i;
    while(l<=r)
    {
        x=q[l++];
        for(i=head[x];i;i=nxt[i])if(dis[to[i]]<0&&f[i]>0)
        {
            dis[to[i]]=dis[x]+1;
            if(to[i]==t)return 1;
            q[++r]=to[i];
        }
    }
    return 0;
}
int dinic(int x,int flow)
{
    if(x==t)return flow;
    int a,tmp=flow;
    for(int i=head[x];i;i=nxt[i])if(dis[to[i]]==dis[x]+1&&f[i])
    {
        a=dinic(to[i],min(f[i],tmp));
        if(!a)dis[to[i]]=-1;
        tmp-=a,f[i]-=a,f[i^1]+=a;
        if(!tmp)return flow;
    }
    return flow-tmp;
}
int maxflow()
{
    int re=0;
    while(bfs())re+=dinic(s,inf);
    return re;
}
int main()
{
    cin>>n;
    s=0,t=n*n+n+1;
    for(int x,j,i=1;i<=n;++i)
    {
        for(j=1;j<=n;++j)
        {
            scanf("%d",&x);
            add((i-1)*n+j,t,x);
            add(n*n+i,(i-1)*n+j,inf);
            add(n*n+j,(i-1)*n+j,inf);
            ans+=x;
        }
    }
    for(int x,i=1;i<=n;++i)
    {
        scanf("%d",&x);
        add(s,n*n+i,x);
    }
    printf("%d\n",ans-maxflow());
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注