loj6045 价

思路

从源点\(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;
}