首页 > 代码库 > BZOJ3438: 小M的作物

BZOJ3438: 小M的作物

3438: 小M的作物

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 247  Solved: 124
[Submit][Status]

Description


 背景

    小M还是个特么喜欢玩MC的孩纸。。。

 描述

    小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
421
232
1
23212

Sample Output


11

样例解释

A耕地种1,2,B耕地种3,收益4+2+3+2=11。

数据范围与约定

对于100%的数据,1<=k< n<= 1000,0<m<=1000保证所有数据及结果不超过2*10^9。

HINT

 

Source

Kpmcup#0 By Greens

题解:
最小割。。。我来搬运题解:
云神:

此题将所有点划分成两个集合,要求获得的点权及附加权最大,可以很容易联想到最小割模型:

我们先把所有的收益加起来,然后建图(令划分到A的点为集合S,划分到B的点为集合T):

对于一个点i,从源点到该点连一条容量为ai的边,再从该点连一条容量为bi的边到汇点,对于一种附加权方案j,添加两个辅助点vj,uj,从源点连一条容量为c1j的边到vj,然后从vj连边到该方案中的所有点,容量为正无穷,从uj连一条容量为c2j的边到汇点,然后对于方案中的所有点连边到uj,容量为正无穷。

然后跑一次最大流算法求出最小割,用总的收益减去最小割即为答案。

证明:假如一个点i划分到T,那么该点划分在S的收益以及于该点有关的附加权方案划分到S的收益将都被割去,对应的就是图中i与源点汇点的连边以及对于方案辅助点的连边。

 代码:

 1 #include<cstdio> 2 #include<cstdlib> 3 #include<cmath> 4 #include<cstring> 5 #include<algorithm> 6 #include<iostream> 7 #include<vector> 8 #include<map> 9 #include<set>10 #include<queue>11 #include<string>12 #define inf 100000000013 #define maxn 10000014 #define maxm 500000015 #define eps 1e-1016 #define ll long long17 #define pa pair<int,int>18 #define for0(i,n) for(int i=0;i<=(n);i++)19 #define for1(i,n) for(int i=1;i<=(n);i++)20 #define for2(i,x,y) for(int i=(x);i<=(y);i++)21 #define for3(i,x,y) for(int i=(x);i>=(y);i--)22 #define mod 100000000723 using namespace std;24 inline int read()25 {26     int x=0,f=1;char ch=getchar();27     while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();}28     while(ch>=0&&ch<=9){x=10*x+ch-0;ch=getchar();}29     return x*f;30 }31 int  n,m,s,t,cnt,sum,maxflow,tot=1,head[maxn],cur[maxn],h[maxn],q[maxn];32 struct edge{int go,next,v;}e[maxm];33 void ins(int x,int y,int z){e[++tot].go=y;e[tot].v=z;e[tot].next=head[x];head[x]=tot;}34 void insert(int x,int y,int z){ins(x,y,z);ins(y,x,0);}35 bool bfs()36 {37     for(int i=s;i<=t;i++)h[i]=-1;38     int l=0,r=1;q[1]=s;h[s]=0;39     while(l<r)40     {41         int x=q[++l];42         for(int i=head[x];i;i=e[i].next)43          if(e[i].v&&h[e[i].go]==-1)44          {45             h[e[i].go]=h[x]+1;q[++r]=e[i].go;46          }47     }48     return h[t]!=-1;49 }50 int dfs(int x,int f)51 {52     if(x==t) return f;53     int tmp,used=0;54     for(int i=head[x];i;i=e[i].next)55      if(e[i].v&&h[e[i].go]==h[x]+1)56     {57         tmp=dfs(e[i].go,min(e[i].v,f-used));58         e[i].v-=tmp;if(e[i].v)cur[x]=i;59         e[i^1].v+=tmp;used+=tmp;60         if(used==f)return f;       61     }62     if(!used) h[x]=-1;63     return used;64 }65 void dinic()66 {67     maxflow=0;68     while(bfs())69     {70         for (int i=s;i<=t;i++)cur[i]=head[i];maxflow+=dfs(s,inf);71     }72 }73 int main()74 {75     freopen("input.txt","r",stdin);76     freopen("output.txt","w",stdout);77     n=read();s=0;t=3005;cnt=n;78     for1(i,n){int x=read();sum+=x;insert(s,i,x);}79     for1(i,n){int x=read();sum+=x;insert(i,t,x);}80     m=read();81     for1(i,m)82     {83         int mm=read(),x=read(),y=read();sum+=x+y;84         insert(s,++cnt,x);insert(++cnt,t,y);85         for1(j,mm)86         {87             int  z=read();88             insert(cnt-1,z,inf);insert(z,cnt,inf);89         }90     }91     dinic();92     cout<<sum-maxflow<<endl;93     return 0;94 }
View Code

因为网络流的模版问题WA了好久。。。

BZOJ3438: 小M的作物