题目描述
小M在MC里开辟了两块巨大的耕地A和B（你可以认为容量是无穷），现在，小P有n中作物的种子，每种作物的种子有1个（就是可以种一棵作物）（用1...n编号）。
现在，第i种作物种植在A中种植可以获得ai的收益，在B中种植可以获得bi的收益，而且，现在还有这么一种神奇的现象，就是某些作物共同种在一块耕地中可以获得额外的收益，小M找到了规则*有m种作物组合，第i个组合中的作物共同种在A中可以获得c1i的额外收益，共同总在B中可以获得c2i的额外收益。
小M很快的算出了种植的最大收益，但是他想要考考你，你能回答他这个问题么？
输入格式
第一行包括一个整数n
第二行包括n个整数，表示ai第三行包括n个整数，表示bi第四行包括一个整数m接下来m行，
对于接下来的第i行：第一个整数ki，表示第i个作物组合*有ki种作物，
接下来两个整数c1i，c2i，接下来ki个整数，表示该组合中的作物编号。
输出格式
只有一行，包括一个整数，表示最大收益
输入输出样例
输入 #13 4 2 1 2 3 2 1 2 3 2 1 2输出 #1
11
说明/提示
样例解释
A耕地种1，2，B耕地种3，收益4+2+3+2=11。
数据范围与约定
1<=k< n<= 1000,0 < m < = 1000 保证所有数据及结果不超过2*10^9。
思路
如果把农作物作为中间点，农场 A 设为源， B 设为汇。
因为对于每个农作物只能种在一个农场中，所以该题可以等效为一个最小割模型。
所以如何对 bonus 的组合建边是关键。
把整个组合点集看作是一个点并拆成出入两点，由A有一条到入点的路，且从出点有一条到B的路，再逐次将待加入的点添加进点集就可以了。
这样能获得的最大值就是总价值 - 最小割
CODE
#include<cstdio> #include<iostream> #include<cstring> #include<queue> #include<vector> #include<algorithm>
using namespace std;
const int maxn = 1e6 + 7; const int inf = 0x3f3f3f3f;
template<class T>inline void read(T &res) { char c;T flag=1; while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0'; while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag; }
struct edge{int from,to,cap,flow;};
struct isap { int n,s,t,p[maxn],d[maxn],cur[maxn],num[maxn]; bool vis[maxn]; vector<int>g[maxn]; vector<edge>edges; void init(int n,int s,int t) { this->n = n; this->s = s; this->t = t; for(int i = 1;i <= n;i++) g[i].clear(); edges.clear(); } void addegde(int from,int to,int cap) { edges.push_back((edge){from, to, cap, 0}); edges.push_back((edge){to, from, 0, 0}); int m = edges.size(); g[from].push_back(m-2); g[to].push_back(m-1); }
int augment() {///找增广路 int x = t,a = inf; while(x!=s) { a = min(a, edges[p[x]].cap - edges[p[x]].flow); x = edges[p[x]].from; } x=t; while(x != s) { edges[p[x]].flow += a; edges[p[x]^1].flow = -a; x = edges[p[x]].from; } return a; } int maxflow() {///更新最大流 int flow = 0; memset(num, 0, sizeof(num)); memset(cur, 0, sizeof(cur)); for(int i = 1; i <= n; i++) num[d[i]]++; int x = s; while(d[s] < n) {///最长的一条链上，最大的下标是nv-1，如果大于等于nv说明已断层 if(x == t) { flow += augment(); x = s;//回退 } bool ok = 0; for(int i = cur[x]; i < g[x].size(); i++) { edge &e = edges[g[x][i]]; if(d[x] == d[e.to] + 1 && e.cap > e.flow) { p[e.to] = g[x][i]; cur[x] = i;x = e.to; ok = 1; break; } } if(!ok) { int m = n-1; for(int i = 0; i < g[x].size();i++) { edge &e=edges[g[x][i]]; if(e.cap>e.flow) m=min(m,d[e.to]); } num[d[x]]--; if(!num[d[x]]) break; d[x] = m+1; num[d[x]]++; cur[x] = 0; if(x != s) x = edges[p[x]].from; } } return flow; } }ISAP;
int n, p, q; int s, t; int tot = 0; int m;
int main() { freopen("data.txt", "r", stdin); read(n); s = n + 1, t = s + 1; ISAP.init(n * n, s, t); for ( int i = 1; i <= n; ++i ) { int x; read(x); tot += x; ISAP.addegde(s, i, x); } for ( int i = 1; i <= n; ++i ) { int x; read(x); tot += x; ISAP.addegde(i, t, x); } read(m); for ( int i = 1; i <= m; ++i ) { int k; read(k); int suma = 0, sumb = 0; read(suma); read(sumb); tot += suma + sumb; ISAP.addegde(s, n + i + 2, suma); ISAP.addegde(n + i + m + 2, t, sumb); for ( int j = 1; j <= k; ++j ) { int x; read(x); ISAP.addegde(n + 2 + i, x, inf); ISAP.addegde(x, n + i + m + 2, inf); } } //cout << tot << " ! " << ISAP.maxflow() << endl; int mincut = ISAP.maxflow(); printf("%d\n",tot - mincut); return 0; }