BZOJ4177: Mike的农场 最小割+网络流

题解：

傻逼最小割。

心血来潮写了个ISAP结果倒数第二的怨念。。。

不错了呢，毕竟早上5点睡的觉，结果7点钟又去打篮球啊。

不得不说人类真是充满活力呢。

现在是8:50，我还能坚持几个小时呢？

代码：

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;

#define inf 0x3f3f3f3f
struct Solver{
	static const int V=100010;
	static const int E=1000010;
	int head[V],next[E],end[E],flow[E],ind;
	int gap[V],d[V],cur[V],stack[V],top;
	inline void reset(){
		ind=top=0;
		memset(head,-1,sizeof head);
	}
	inline void addedge(int a,int b,int f){
		int q=ind++;
		end[q]=b;
		next[q]=head[a];
		head[a]=q;
		flow[q]=f;
	}
	inline void make(int a,int b,int f){
		addedge(a,b,f);
		addedge(b,a,0);
	}
	inline void bfs(int t){
		static int q[V];
		memset(d,-1,sizeof d);
		memset(gap,0,sizeof gap);
		int fr=0,ta=0,i,j;
		++gap[d[q[ta++]=t]=0];
		while(fr!=ta){
			i=q[fr++];
			for(j=head[i];j!=-1;j=next[j])
				if(d[end[j]]==-1)
					++gap[d[q[ta++]=end[j]]=d[i]+1];
		}
	}
	inline int Maxflow(int s,int t){
		memcpy(cur,head,sizeof cur);
		bfs(t);
		int mn,ins,i,u=s,re=0;
		while(d[s]<t-s+1){
			if(u==t){
				for(mn=inf,i=0;i<top;++i)
					if(mn>flow[stack[i]])
						mn=flow[stack[i]],ins=i;
				for(re+=mn,i=0;i<top;++i){
					flow[stack[i]]-=mn;
					flow[stack[i]^1]+=mn;
				}
				u=end[stack[top=ins]^1];
			}
			if(u!=t&&!gap[d[u]-1])
				break;
			ins=-1;
			for(int j=head[u];j!=-1;j=next[j])
				if(flow[j]&&d[u]==d[end[j]]+1){
					ins=j;
					break;
				}
			if(ins!=-1){
				stack[top++]=cur[u]=ins;
				u=end[ins];
			}
			else{
				mn=t-s+1;
				for(int j=head[u];j!=-1;j=next[j])
					if(flow[j]&&mn>d[end[j]]){
						cur[u]=j;
						mn=d[end[j]];
					}
				if(!--gap[d[u]])
					break;
				++gap[d[u]=mn+1];
				if(u!=s)
					u=end[stack[--top]^1];
			}
		}
		return re;
	}
}g;

int main(){
#ifndef ONLINE_JUDGE
	freopen("tt.in","r",stdin);
#endif
	int n,m,p,i,j;
	cin>>n>>m>>p;
	g.reset();
	int x,s=0,t=n+p+1,ans=0;
	for(i=1;i<=n;++i){
		scanf("%d",&x);
		ans+=x;
		g.make(s,i,x);
	}
	for(i=1;i<=n;++i){
		scanf("%d",&x);
		ans+=x;
		g.make(i,t,x);
	}
	int a,b,c;
	while(m--){
		scanf("%d%d%d",&a,&b,&c);
		g.make(a,b,c);
		g.make(b,a,c);
	}
	int num;
	for(i=1;i<=p;++i){
		scanf("%d%d%d",&num,&a,&b);
		ans+=b;
		while(num--){
			scanf("%d",&x);
			if(a==0)
				g.make(n+i,x,inf);
			else
				g.make(x,n+i,inf);
		}
		if(a==0)
			g.make(s,n+i,b);
		else
			g.make(n+i,t,b);
	}
	cout<<ans-g.Maxflow(s,t)<<endl;
	return 0;
}