[BZOJ-1280]猪 题解

#include<bits/stdc++.h>
using namespace std;

const int N=2e5+5,M=1500,INF=0x3f3f3f3f;
int h[M],nxt[N],w[N],ver[N],co=1;
int a[M],pre[N];
int n,m,s,t;
int tmp[M];

void add(int x,int y,int z){
	nxt[++co]=h[x],h[x]=co,ver[co]=y,w[co]=z;
	nxt[++co]=h[y],h[y]=co,ver[co]=x,w[co]=0;
}

int d[M],no[M];
bool bfs(){
	memset(d,0,sizeof d);
	queue<int> q;
	d[s]=1,no[s]=h[s];q.push(s);
	while(q.size()){
		int x=q.front();q.pop();
		for(int i=h[x];i;i=nxt[i]){
			int y=ver[i];
			if(!d[y] && w[i]){
				d[y]=d[x]+1,no[y]=h[y];
				q.push(y);
				if(y==t)	return 1;
			}
		}
	}
	return 0;
}

int dfs(int x,int fl){
	if(x==t)	return fl;
	int res=fl,i,k;
	for(i=no[x];i && res;i=nxt[i]){
		int y=ver[i];
		if(d[y]==d[x]+1 && w[i]){
			k=dfs(y,min(res,w[i]));
			if(!k)	d[y]=0;
			res-=k;
			w[i]-=k;
			w[i^1]+=k;
		}
	}
	no[x]=i;
	return fl-res;
} 

int main(){
	
	cin>>n>>m;
	s=1,t=2;
	for(int i=1;i<=n;++i)	cin>>a[i],pre[i+2]=i+2;
	for(int i=1;i<=m;++i){
		int k,x,y;cin>>k;
		
		for(int j=1;j<=k;++j){
			cin>>x;y=pre[x+2];
			if(y==x+2)	tmp[1]+=a[x];
			else	tmp[y]=INF;
			pre[x+2]=i+n+2;
		}
		
		for(int j=1;j<n+i+2;++j){
			if(tmp[j])	add(j,i+n+2,tmp[j]),tmp[j]=0;
		}
		cin>>k;
		add(i+n+2,t,k);
	}
	
	int flow=0,ans=0;
	while(bfs()){
		while(flow=dfs(1,INF))	ans+=flow;
	}
	cout<<ans;
	
	return 0;
}