[BZOJ3438]小M的作物 最小割



将一些点划分为两个点集,每个点在每个点集中有收益,且某些固定的点组合出现在同一个点集中会有buff,求最大收益.
最小割的思想在于将最大收益转化为最小损失处理,这也是最大权闭合子图的求解思路.
源点朝每个作物连容量为ai的边,作物朝汇点连容量为bi的边;对于每个buff拆成两个点x和y,s向x连边,容量为c2i,x向所有成员连边,容量为INF;y向t连边,容量为c1i,所有成员向y连边,容量为INF.所有收益-最小割就是答案.

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 23333
#define M 2333333
using namespace std;
const int inf=2147483647;
int s=0,t=20000,n,m,head[N],to[M],nxt[M],f[M],tot=1;
long long ans;
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,y,i;
    while(l<=r)
    {
        x=q[l++];
        for(i=head[x];i;i=nxt[i])
        {
            y=to[i];
            if(dis[y]<0&&f[i]>0)
            {
                dis[y]=dis[x]+1;
                if(y==t)return 1;
                q[++r]=y;
            }
        }
    }
    return 0;
}
int dinic(int x,int flow)
{
    if(x==t)return flow;
    int a,temp=flow;
    for(int i=head[x];i;i=nxt[i])if(dis[to[i]]==dis[x]+1&&f[i]>0)
    {
        a=dinic(to[i],min(temp,f[i]));
        if(!a)dis[to[i]]=-1;
        temp-=a,f[i]-=a,f[i^1]+=a;
        if(!temp)return flow;
    }
    return flow-temp;
}
int maxflow()
{
    int re=0;
    while(bfs())re+=dinic(s,inf);
    return re;
}
int main()
{
    cin>>n;
    for(int x,i=1;i<=n;++i)
    {
        scanf("%d",&x);
        ans+=x;
        add(s,i,x);
    }
    for(int x,i=1;i<=n;++i)
    {
        scanf("%d",&x);
        ans+=x;
        add(i,t,x);
    }
    cin>>m;
    for(int k,c1,c2,x,j,i=1;i<=m;++i)
    {
        scanf("%d%d%d",&k,&c1,&c2);
        ans+=c1,ans+=c2;
        add(s,n+i,c1);
        add(m+n+i,t,c2);
        for(j=1;j<=k;++j)
        {
            scanf("%d",&x);
            add(n+i,x,inf);
            add(x,m+n+i,inf);
        }
    }
    printf("%lld\n",ans-maxflow());
    return 0;
}

发表评论

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