洛谷 P1361 小M的作物

题面

题意

有n个作物,A,B两块地,将它们种在A,B中的一块,每个作物种在两块地上分别有一个收益,有m种组合,若这个组合内的作物都在一块地内则有额外收益,求最大收益.

做法

这题与洛谷 P3355 骑士共存问题有些相似,都是转化为最小割的问题.

首先假设每种作物均有两个,分别种在A,B上,现在要每种作物都要拔掉一个,那么在跑最大流时,有流量则代表这种做法不采用,最后用总收益减去最大流量即可.

具体建边方法

超级源点向每个点连一条流量为种在A地的收益的边,每个点向超级汇点连一条流量为种在B地的收益的边,接着考虑m种组合,对于每种组合新建两个点,表示都种在A或都种在B,在此记为a,b.超级源点向a连一条流量为该组合种在A的收益的边,a向组合内的所有点都连一条流量为INF的边.b向超级汇点连一条流量为该组合种在B的收益的边,组合内的所有点都向b连一条流量为INF的边.

这样就可以保证,如果有一种作物k不种在A地即超级源点连向k的边有流量,那么超级源点向包括k的组合中的a也一定会有流量,保证了这种组合不可取.

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define INF 0x3f3f3f3f
#define N 30100
#define M 2000100
using namespace std;

int n,m,s,t,first[N],deep[N],bb=,sum,ans,cur[N],b[N];
struct Bn
{
    int to,next,quan;
}bn[M];
queue<int>que;

inline void add(int u,int v,int w)
{
    bb++;
    bn[bb].to=v;
    bn[bb].next=first[u];
    bn[bb].quan=w;
    first[u]=bb;
}

inline void ad(int u,int v,int w)
{
    add(u,v,w);
    add(v,u,);
}

inline bool bfs()
{
    int p,q;
    for(;!que.empty();que.pop());
    memset(deep,,sizeof(deep));
    deep[s]=;
    que.push(s);
    for(;!que.empty()&&!deep[t];)
    {
        q=que.front();
        que.pop();
        for(p=first[q];p!=-;p=bn[p].next)
        {
            if(!bn[p].quan||deep[bn[p].to]) continue;
            deep[bn[p].to]=deep[q]+;
            que.push(bn[p].to);
        }
    }
    return deep[t];
}

int dfs(int now,int mn)
{
    if(now==t)
        return mn;
    int res;
    for(int &p=cur[now];p!=-;p=bn[p].next)
    {
        if(deep[bn[p].to]!=deep[now]+||!bn[p].quan) continue;
        res=dfs(bn[p].to,min(mn,bn[p].quan));
        if(res)
        {
            bn[p].quan-=res;
            bn[p^].quan+=res;
            return res;
        }
    }
    return ;
}

int main()
{
    memset(first,-,sizeof(first));
    int i,j,p,q;
    cin>>n;
    for(i=;i<=n;i++)
    {
        scanf("%d",&p);
        ad(s,i,p);
        ans+=p;
    }
    for(i=;i<=n;i++)
    {
        scanf("%d",&b[i]);
    }
    cin>>m;
    t=n+m*+;
    for(i=;i<=n;i++)
    {
        ad(i,t,b[i]);
        ans+=b[i];
    }
    for(i=;i<=m;i++)
    {
        scanf("%d%d",&p,&q);
        ad(s,n+i,q);
        ans+=q;
        scanf("%d",&q);
        ad(n+m+i,t,q);
        ans+=q;
        for(j=;j<=p;j++)
        {
            scanf("%d",&q);
            ad(n+i,q,INF);
            ad(q,n+m+i,INF);
        }
    }
    for(;bfs();)
    {
        memcpy(cur,first,sizeof(first));
//      for(i=s;i<=t;i++) cur[i]=first[i];
        for(p=dfs(s,INF);p;ans-=p,p=dfs(s,INF));
    }
    cout<<ans;
}