LOJ

CF 原题

分析

感觉很像最小权闭合子图。为了方便把所有费用取负。考虑这样的连边方式

• 源点向每种药连容量为 $+\infty+p_i$ 的边。
• 每种药向所需的药材连容量为 $+\infty$ 的边。
• 每种药材向汇点连容量为 $+\infty$ 的边。

拿最小割减去所有 $+\infty+p_i$ 的和即为答案（因为取了负）。

下面是正确性理解：

首先可以发现，第二种的边是不会割的，如果割了换成第三种边答案相同。

那么如果割了一条与源点相连的边，代表放弃选择这种药；如果割了一条与汇点相连的边，代表选择这种药材。

进一步，我们一定会恰好割掉 $n$ 条边，即不选择的药和选择的药材数量之和为 $n$。又因为不选择的药和选择的药数量之和为 $n$，所以在最小割中选择的药材和选择的药是相等的，即最小割一定满足条件。

而当相减时所有的 $+\infty$ 恰好抵消，只剩下一些 $p_i$ 的和，即为答案。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=300+10;
const int V=600+10,E=100000+10;
const int inf=1e7;

int n;

struct edge { int v,w,nxt; } e[E<<1];
int head[V];
void addEdge(int u,int v,int w) {
    static int cnt=1;
    e[++cnt]=(edge){v,w,head[u]},head[u]=cnt;
    e[++cnt]=(edge){u,0,head[v]},head[v]=cnt;
}

int lv[V],S,T;
int bfs() {
    memset(lv,0,sizeof(lv)),lv[S]=1;
    queue<int> Q; 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 (e[i].w&&!lv[v]) lv[v]=lv[u]+1,Q.push(v);
        }
    }
    return lv[T]!=0;
}
int dfs(int u,int r) {
    if (u==T||!r) return r;
    int a=0;
    for (int i=head[u];i;i=e[i].nxt) {
        int v=e[i].v;
        if (e[i].w&&lv[v]==lv[u]+1) {
            int t=dfs(v,min(r,e[i].w));
            e[i].w-=t,e[i^1].w+=t,a+=t,r-=t;
            if (!r) break;
        }
    }
    if (!a) lv[u]=0;
    return a;
}
int dinic() { int s=0; for (;bfs();s+=dfs(S,2e9)); return s; }

int main() {
    n=read(),S=0,T=n<<1|1; int ans=0;
    for (int i=1;i<=n;++i)
        for (int t=read();t;--t) addEdge(i,read()+n,inf);
    for (int i=1;i<=n;++i) {
        int w=inf-read(); ans+=w; addEdge(S,i,w);
    }
    for (int i=1;i<=n;++i) addEdge(i+n,T,inf);
    printf("%d\n",dinic()-ans);
    return 0;
}