[文章目录]
Description
小M在MC里开辟了两块巨大的耕地A和B（你可以认为容量是无穷），现在，小P有n中作物的种子，每种作物的种子有1个（就是可以种一棵作物）（用1...n编号），现在，第i种作物种植在A中种植可以获得ai的收益，在B中种植可以获得bi的收益，而且，现在还有这么一种神奇的现象，就是某些作物共同种在一块耕地中可以获得额外的收益，小M找到了规则中共有m种作物组合，第i个组合中的作物共同种在A中可以获得c1i的额外收益，共同总在B中可以获得c2i的额外收益，算出种植的最大收益.1<=k< n<= 1000,0 < m < = 1000
网络流最小割。每种作物建一个点，s向它连一条ai为流量的边，它向t连一条流量为bi的边，对于每个组合，如果为a种，那么新建一个节点，s向其连边，流量为ci，它向所有组合中的节点连边，流量为inf，发现，只有一个节点选了b，那么它必须被割掉，符合题意。反之同理。
最小割这个工具感觉很神啊。。。终于明白为什么网络流难在建图了。。
#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int ans;
const int inf=0x3f3f3f3f;
int n,m,s,t,tot,z[1100];
int head[3100],to[5000000],f[5000000],nxt[5000000],cnt=1;
inline void add(int x,int y,int z)
{
to[++cnt]=y; nxt[cnt]=head[x]; head[x]=cnt; f[cnt]=z;
to[++cnt]=x; nxt[cnt]=head[y]; head[y]=cnt; f[cnt]=0;
}
int dis[3100];
queue<int>q;
bool bfs()
{
memset(dis,-1,sizeof dis);
while(!q.empty()) q.pop();
q.push(s); dis[s]=0; int x; int i;
while(!q.empty())
{
x=q.front(); q.pop();
for(i=head[x];i;i=nxt[i]) if(f[i]>0&&dis[to[i]]==-1)
{
dis[to[i]]=dis[x]+1;
if(to[i]==t) return true;
q.push(to[i]);
}
}
return false;
}
int dinic(int x,int flow)
{
if(x==t) return flow;
int xx,tmp=flow;
for(int i=head[x];i;i=nxt[i])
if(f[i]>0&&dis[to[i]]==dis[x]+1)
{
xx=dinic(to[i],min(f[i],tmp));
if(!xx) dis[to[i]]=-1;
f[i]-=xx; f[i^1]+=xx; tmp-=xx;
if(!tmp) break;
}
return flow-tmp;
}
int main()
{
scanf("%d",&n); s=n+1,t=s+1; tot=t; int x;
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); int c1,c2;
while(m--)
{
scanf("%d%d%d",&x,&c1,&c2); ans+=(c1+c2);
for(int i=1;i<=x;++i) scanf("%d",z+i);
++tot; add(s,tot,c1);
for(int i=1;i<=x;++i) add(tot,z[i],inf);
++tot; add(tot,t,c2);
for(int i=1;i<=x;++i) add(z[i],tot,inf);
}
while(bfs()) ans-=dinic(s,inf);
printf("%d",ans);
return 0;
}