【BZOJ-3438】小M的作物 最小割 + 最大权闭合图

时间：2023-12-14 11:32:44

3438: 小M的作物

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit:
825  Solved: 368
[Submit][Status][Discuss]

Description

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

Input

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

Output

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

Sample Input

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

Sample Output

11
样例解释A耕地种1，2，B耕地种3，收益4+2+3+2=11。
1<=k< n<=
1000,0 < m < = 1000 保证所有数据及结果不超过2*10^9。

HINT

Source

Kpmcup#0 By Greens

Solution

这不是傻逼题？？

有种“文理分科”的既视感，反正也差不多TAT

又是最大全闭合图

对于单个作物  连S-->x  表示种在A中，容量为收益，  x-->T 表示种在B中容量为收益

对于多种集合 新建一个总点  S-->a' 表示都种在A，容量为收益， 再由a‘连所有集合中的点，  b’-->T 原理一样

最后ans=tot-mincut

Code

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<queue>

using namespace std;

int read()

{

    int x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define maxm 3000010

#define maxn 3010

int n,m,tot;

struct EdgeNode{int next,to,cap;}edge[maxm];

int head[maxn],cnt=;

void add(int u,int v,int w) {cnt++; edge[cnt].next=head[u]; head[u]=cnt; edge[cnt].to=v; edge[cnt].cap=w;}

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

#define inf 0x7fffffff

int dis[maxn],cur[maxn],S,T;

bool bfs()

{

    queue<int>q;

    for (int i=S; i<=T; i++) dis[i]=-;

    q.push(S); dis[S]=;

    while (!q.empty())

        {

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

            for (int i=head[now]; i; i=edge[i].next)

                if (edge[i].cap && dis[edge[i].to]==-)

                    dis[edge[i].to]=dis[now]+,q.push(edge[i].to);

        }

    return dis[T]!=-;

}

int dfs(int x,int low)

{

    if (x==T) return low;

    int used=,w;

    for (int i=cur[x]; i; i=edge[i].next)

        if (edge[i].cap && dis[edge[i].to]==dis[x]+)

            {

                w=dfs(edge[i].to,min(edge[i].cap,low-used));

                edge[i].cap-=w; edge[i^].cap+=w; used+=w;

                if (edge[i].cap) cur[x]=i; if (low==used) return used;

            }

    if (!used) dis[x]=-;

    return used;

}

int dinic()

{

    int tmp=;

    while (bfs())

        {

            for (int i=S; i<=T; i++) cur[i]=head[i];

            tmp+=dfs(S,inf);

        }

    return tmp;

}

int a[maxn],b[maxn];

int main()

{

    n=read();

    for (int x,i=; i<=n; i++) a[i]=read(),tot+=a[i];

    for (int x,i=; i<=n; i++) b[i]=read(),tot+=b[i];

    m=read();

    S=,T=n+*m+;

    for (int i=; i<=n; i++) insert(S,i,a[i]),insert(i,T,b[i]);

    for (int nn,x,y,i=; i<=m; i++)

        {

            nn=read(); x=read(),y=read(); tot+=x+y;

            insert(S,++n,x); insert(++n,T,y);

            for (int z,j=; j<=nn; j++) z=read(),insert(z,n,inf),insert(n-,z,inf);

        }

    printf("%d\n",tot-dinic());

    return ;

}

相关文章