3438

思路:

  最小割(完全不懂看的题解);

  s向每个作物连边,s-x ai,x-t bi;

  然后s向作物集合连边,cia;

  作物集合拆点向t连边,cib;

  作物集合第一个点向作物连边INF;

  作物向作物集合第二个点连边INF;

  ans=sum-maxflow;

来,上代码:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm> using namespace std; #define maxn 10005
#define maxm 2000005
#define INF 0x7fffffff int n,s,t,head[maxn<<],E[maxm],V[maxm],F[maxm],cnt=;
int ai[maxn],bi[maxn],m,que[maxm<<],deep[maxn<<],ans; bool if_[maxn<<]; inline void in(int &now)
{
char Cget=getchar();now=;
while(Cget>''||Cget<'') Cget=getchar();
while(Cget>=''&&Cget<='')
{
now=now*+Cget-'';
Cget=getchar();
}
} inline void edge_add(int u,int v,int f)
{
E[++cnt]=head[u],V[cnt]=v,F[cnt]=f,head[u]=cnt;
E[++cnt]=head[v],V[cnt]=u,F[cnt]=,head[v]=cnt;
} inline bool bfs()
{
for(int i=s;i<=t;i++) deep[i]=-,if_[i]=false;
int h=,tail=;deep[s]=,que[]=s,if_[s]=true;
while(h<tail)
{
int now=que[h++];if_[now]=false;
for(int i=head[now];i;i=E[i])
{
if(F[i]>&&deep[V[i]]<)
{
deep[V[i]]=deep[now]+;
if(V[i]==t) return true;
if(!if_[V[i]]) que[tail++]=V[i],if_[V[i]]=true;
}
}
}
return false;
} int flowing(int now,int flow)
{
if(now==t||flow<=) return flow;
int oldflow=;
for(int i=head[now];i;i=E[i])
{
if(F[i]<=||deep[V[i]]!=deep[now]+) continue;
int pos=flowing(V[i],min(F[i],flow));
F[i]-=pos,F[i^]+=pos;
flow-=pos,oldflow+=pos;
if(flow==) return oldflow;
}
if(oldflow==) deep[now]=-;
return oldflow;
} int main()
{
in(n);
for(int i=;i<=n;i++) in(ai[i]),ans+=ai[i];
for(int i=;i<=n;i++) in(bi[i]),ans+=bi[i];
in(m),t=n+m*+;
for(int i=;i<=m;i++)
{
int ki,cia,cib,pos;
in(ki),in(cia),in(cib),ans+=cia,ans+=cib;
edge_add(s,n+i,cia);
edge_add(n+m+i,t,cib);
for(int j=;j<=ki;j++)
{
in(pos);
edge_add(n+i,pos,INF);
edge_add(pos,n+m+i,INF);
}
}
for(int i=;i<=n;i++)
{
edge_add(s,i,ai[i]);
edge_add(i,t,bi[i]);
}
while(bfs()) ans-=flowing(s,INF);
cout<<ans;
return ;
}
05-11 01:22