思路
从源点(s)向每种药连一条边权为(-p+inf)的边。从每种药向他所需要的药材连一条边权为(inf)的边。从每种药材向汇点(t)连一条边权为(inf)的边。
(inf>inf)
用最小割减去源点连向药材的边权之和。
代码
#include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<queue> #include<cmath> #include<ctime> #include<bitset> using namespace std; typedef long long ll; const int n = 100010,inf = 5e6,inf = 1e9; 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; } int n; int s,t; struct node { int v,nxt,w; }e[n << 1]; int head[n],ejs = 1; void add(int u,int v,int w) { e[++ejs].v = v;e[ejs].nxt = head[u];head[u] = ejs;e[ejs].w = w; e[++ejs].v = u;e[ejs].nxt = head[v];head[v] = ejs;e[ejs].w = 0; } int dep[n]; queue<int>q; int bfs() { memset(dep,0,sizeof(dep)); while(!q.empty()) q.pop(); q.push(s);dep[s] = 1; 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 <= 0) continue; dep[v] = dep[u] + 1; q.push(v); if(v == t) return 1; } } return 0; } int dfs(int u,int now) { if(u == t) return now; int ret = 0; for(int i = head[u];i;i = e[i].nxt) { int v = e[i].v; if(e[i].w > 0 && dep[v] == dep[u] + 1) { int k = dfs(v,min(now - ret,e[i].w)); ret += k; e[i].w -= k; e[i ^ 1].w += k; if(ret == now) return ret; } } return ret; } ll dinic() { ll ans = 0; while(bfs()) ans += dfs(s,inf); return ans; } int main() { n = read(); ll tot = 0; s = n * 2 + 1,t = s + 1; for(int i = 1;i <= n;++i) { int k = read(); for(int j = 1;j <= k;++j) { int t = read(); add(i,t + n,inf); } } for(int i = 1;i <= n;++i) { int w = read(); tot += inf - w; add(s,i,inf - w); add(i + n,t,inf); } cout<<dinic() - tot; return 0; }
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/c-cdevelopment/605297.html