题目链接
思路
先考虑没有额外收益的时候怎么做。
从(s)向第(i)点连一条容量为(a_i)边,表示种在(a)中的收益。
从第(i)个点向(t)连一条容量为(b_i)的边,表示种在(b)中的收益。
然后求出来最小割,用总收益减去即可。
完成之后如下图:
然后考虑如何处理额外收益
对于每一个额外的收益,我们先新建一个点(x),表示全部建在(a)的收益。
需要保证如果不割掉这条边,那么就说明这些点全部建在(a).所以这些点向(t)的连边必须全部割掉。
那么就从(s)向(x)连边,从(x)向该组合中所有点连边。
对于全部建在b处的额外收益,同理。
加入上图中含有组合({1,2}),建图之后如下:
然后用总收益减去最小割就是答案。
代码
/* * @author: wxyww * @date: 2019-06-10 08:33:40 * @last modified time: 2019-06-10 09:10:44 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> using namespace std; typedef long long ll; const int n = 10100,m = 5000100,inf = 2e9; ll read() { ll x=0,f=1;char c=getchar(); while(c<'0'||c>'9') { if(c=='-') f=-1; c=getchar(); } while(c>='0'&&c<='9') { x=x*10+c-'0'; c=getchar(); } return x*f; } struct node { int v,nxt,w; }e[m]; queue<int>q; int dep[n],head[n],ejs = 1; void add(int u,int v,int w) { e[++ejs].v = v;e[ejs].w = w;e[ejs].nxt = head[u];head[u] = ejs; e[++ejs].v = u;e[ejs].w = 0;e[ejs].nxt = head[v];head[v] = ejs; } int s,t,cur[n]; bool bfs() { memset(dep,0,sizeof(dep)); while(!q.empty()) q.pop(); dep[s] = 1;q.push(s); while(!q.empty()) { int u = q.front();q.pop(); for(int i = head[u];i;i = e[i].nxt) { int v = e[i].v; if(!dep[v] && e[i].w) { dep[v] = dep[u] + 1; q.push(v); if(v == t) return true; } } } return false; } int dfs(int u,int now) { if(u == t) return now; int ret = 0; for(int &i = cur[u];i;i = e[i].nxt) { int v = e[i].v; if(dep[v] == dep[u] + 1 && e[i].w) { int k = dfs(v,min(now - ret,e[i].w)); e[i].w -= k;e[i ^ 1].w += k; ret += k; if(ret == now) return ret; } } return ret; } int dinic() { int ret = 0; while(bfs()) { memcpy(cur,head,sizeof(cur)); ret += dfs(s,inf); } return ret; } int ans = 0; int main() { int n = read(); s = n + 1,t = s + 1; for(int i = 1;i <= n;++i) { int k = read();ans += k;add(s,i,k); } for(int i = 1;i <= n;++i) { int k = read();ans += k;add(i,t,k); } int m = read(); int cnt = n + 2; for(int i = 1;i <= m;++i) { int k = read(),c1 = read(),c2 = read(); int x = ++cnt,x_ = ++cnt; ans += c1,ans += c2; add(s,x,c1);add(x_,t,c2); for(int j = 1;j <= k;++j) { int x = read(); add(x,x,inf);add(x,x_,inf); } } cout<<ans - dinic(); return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/603093.html