BZOJ3438小M的作物——最小割

时间：2022-03-24 02:46:18

题目描述

小M在MC里开辟了两块巨大的耕地A和B（你可以认为容量是无穷），现在，小P有n中作物的种子，每种作物的种子
有1个（就是可以种一棵作物）（用1...n编号），现在，第i种作物种植在A中种植可以获得ai的收益，在B中种植
可以获得bi的收益，而且，现在还有这么一种神奇的现象，就是某些作物共同种在一块耕地中可以获得额外的收益
，小M找到了规则*有m种作物组合，第i个组合中的作物共同种在A中可以获得c1i的额外收益，共同总在B中可以
获得c2i的额外收益，所以，小M很快的算出了种植的最大收益，但是他想要考考你，你能回答他这个问题么？

输入

第一行包括一个整数n
第二行包括n个整数，表示ai第三行包括n个整数，表示bi第四行包括一个整数m接下来m行，
对于接下来的第i行：第一个整数ki，表示第i个作物组合*有ki种作物，
接下来两个整数c1i，c2i，接下来ki个整数，表示该组合中的作物编号。输出格式

输出

只有一行，包括一个整数，表示最大收益

样例输入

3
4 2 1
2 3 2
1
2 3 2 1 2

样例输出

11
样例解释A耕地种1，2，B耕地种3，收益4+2+3+2=11。
1<=k< n<= 1000,0 < m < = 1000 保证所有数据及结果不超过2*10^9。
源汇点分别表示选择种在$A$还是$B$上。将源点与每种作物连边，流量为选$A$的收益；每种作物与汇点连边，流量为$B$的收益。对于每种组合收益可以将它看成两种：一种是选$A$的组合，一种是选$B$的组合。如果是选$A$的组合，新建一个点，将源点连向新建点，流量为对应收益；再将新建点连向组合中所有点，流量为$INF$。如果是选$B$的组合，新建点连向汇点，流量为对应收益；再将组合中所有点连向新建点，流量为$INF$。答案就是总收益$-$最小割。由于边数较多，需要$dinic$加上多种优化。 
#include<set>

#include<map>

#include<queue>

#include<stack>

#include<cmath>

#include<cstdio>

#include<vector>

#include<bitset>

#include<cstring>

#include<iostream>

#include<algorithm>

#define INF 0x3f3f3f3f

#define ll long long

using namespace std;

int head[4000];

int to[4000000];

int next[4000000];

int val[4000000];

int d[4000];

int q[4000];

int back[4000];

int S,T;

int x,y,k;

int n,m;

int tot=1;

int ans;

void add(int x,int y,int v)

{

    tot++;

    next[tot]=back[x];

    back[x]=tot;

    to[tot]=y;

    val[tot]=v;

    tot++;

    next[tot]=back[y];

    back[y]=tot;

    to[tot]=x;

    val[tot]=0;

}

bool bfs(int S,int T)

{

    int r=0;

    int l=0;

    memset(d,-1,sizeof(d));

    q[r++]=T;

    d[T]=2;

    while(l<r)

    {

        int now=q[l];

        for(int i=back[now];i;i=next[i])

        {

            if(d[to[i]]==-1&&val[i^1]!=0)

            {

                d[to[i]]=d[now]+1;

                q[r++]=to[i];

            }

        }

        l++;

    }

    if(d[S]==-1)

    {

        return false;

    }

    else

    {

        return true;

    }

}

int dfs(int x,int flow)

{

    if(x==T)

    {

        return flow;

    }

    int now_flow;

    int used=0;

    for(int &i=head[x];i;i=next[i])

    {

        if(d[to[i]]==d[x]-1&&val[i]!=0)

        {

            now_flow=dfs(to[i],min(flow-used,val[i]));

            val[i]-=now_flow;

            val[i^1]+=now_flow;

            used+=now_flow;

            if(now_flow==flow)

            {

                return flow;

            }

        }

    }

    if(used==0)

    {

        d[x]=-1;

    }

    return used;

}

int dinic()

{

	int res=0;

    while(bfs(S,T))

    {

        memcpy(head,back,sizeof(back));

        res+=dfs(S,0x3f3f3f3f);

    }

    return res;

}

int main()

{

	scanf("%d",&n);

	S=n+1;

	T=n+2;

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

	{

		scanf("%d",&x);

		add(S,i,x);

		ans+=x;

	}

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

	{

		scanf("%d",&x);

		add(i,T,x);

		ans+=x;

	}

	scanf("%d",&m);

	for(int i=1;i<=m;i++)

	{

		scanf("%d%d%d",&k,&x,&y);

		add(S,n+2+i,x);

		ans+=x;

		add(n+2+i+m,T,y);

		ans+=y;

		for(int j=1;j<=k;j++)

		{

			scanf("%d",&x);

			add(n+2+i,x,INF);

			add(x,n+2+i+m,INF);

		}

	}

	printf("%d",ans-dinic());

}

相关文章