Description
Mike有一个农场，这个农场n个牲畜围栏，如今他想在每一个牲畜围栏中养一仅仅动物，每仅仅动物能够是牛或羊，并且每一个牲畜围栏中的饲养条件都不同，当中第i个牲畜围栏中的动物长大后，每仅仅牛能够卖a[i]元，每仅仅羊能够卖b[i]元，为了防止牛羊之间相互影响，Mike找到了m条规律。每条规律给出一个三元组(i, j, k)表示假设第i个围栏和第j个围栏养的是不同的动物，那么Mike就须要花费k的代价请人帮忙处理牛羊之间的影响。只是同一时候Mike也发现k条特殊的规则(S, a, b)。表示假设S中全部牲畜围栏中都养的是动物a。那么Mike能够获得b的额外收入。如今Mike想知道他该在哪些围栏中饲养什么动物才干使得总收益最大。为了简化问题。你仅仅须要输出最大收益。
Input
第一行三个整数n、m、k，表示一共同拥有n个围栏，m条规律。k条规则。
第二行有n个整数，表示a[i]。
第三行有n个整数，表示b[i]。
接下来m行。每行有三个整数(i, j, k)表示一条规则。
再接下来k行，每行一開始有三个整数t、a和b。表示一条规则(S, a, b)，当中S的大小为t。接下来
t个整数表示S中的元素（a为0表示全为牛。a为1表示全为羊）。
Output
输出一个整数ans，表示最大收益。
Sample Input
4 2 1
1 2 3 1
2 3 1 2
1 2 3
1 3 2
2 0 100 1 2
Sample Output
108
HINT
对于100的数据，n <= 5000, m <= 5000, k <= 5000, a = 0 or 1。
题解与吐槽：
傻逼网络流
然后听取了tkd的建议拆了点。。。
wa后发现拆点毫无意义并且会影响正确性从源点向每一个点连一条流量为ai的边，每一个点向汇点连一条流量为bi的边。于是每一种割法相应一种选择。然后考虑另外一种限制，我们向有关系的两点互连流量为k的边，意会一下。
第三种的话我们再加上一个新点。假设要求是割掉集合中的点与汇点的边，于是从源点向这个点连流量为收益大小的边，在从这个点向集合中的点连流量无穷大的边。还有一种情况同理。
于是就完了。
请无视掉那个奇怪的typedef。事实上它的含义是tkd神犇
#includeusing namespace std;typedef long long ll;typedef double db;typedef long long tkdsb;const tkdsb inf=0x3f3f3f3f3f3f;tkdsb getint(){ char c=getchar(); tkdsb f=1,g=0; while(c>'9' || c<'0'){ if(c=='-')f=-1;c=getchar();} while(c<='9' && c>='0')g=(g<<3)+(g<<1)+c-'0',c=getchar(); return f*g;}const tkdsb maxn=40005;tkdsb n,m,k;struct edge{ tkdsb from,to,cap;};tkdsb s,t;vector g[maxn];vector eds;void addedge(tkdsb from,tkdsb to,tkdsb cap){ g[from].push_back(eds.size()); eds.push_back((edge){from,to,cap}); g[to].push_back(eds.size()); eds.push_back((edge){to,from,0});}tkdsb d[maxn];queue q;bool bfs(){ memset(d,-1,sizeof d); d[s]=0; q.push(s); while(!q.empty()) { tkdsb x=q.front();q.pop(); for(vector ::iterator it=g[x].begin();it!=g[x].end();it++) { edge e=eds[*it]; if(d[e.to]==-1 && e.cap>0) { d[e.to]=d[x]+1; q.push(e.to); } } } return d[t]!=-1;}tkdsb cur[maxn];tkdsb dfs(tkdsb x,tkdsb f){ if(x==t || f==0)return f; tkdsb used=0; tkdsb temp; for(tkdsb i=cur[x];i