LOJ_6045_「雅礼集训 2017 Day8」价 _最小割
描述：
有$n$种减肥药，$n$种药材，每种减肥药有一些对应的药材和一个收益。
假设选择吃下$K$种减肥药，那么需要这$K$种减肥药包含的药材也等于$K$时才会有效果。
求最小收益，收益可能是负的。保证有完美匹配。
分析：
先把所有权值取相反数求最大收益，因为最小收益看着很难受。
$S$->减肥药($inf$+收益)，减肥药->药材($inf$),药材->$T$($inf$)。
然后求最小割，答案就是$S$连出去的边的容量和-最小割。
性质1：割中间的边不会更优。
割左边的边表示不选这种减肥药，割右边的边表示选这种药材。
性质2：加上$inf$后保证左边选取的点数等于右边选取的点数。
性质3：题目存在完美匹配。因此答案一定小于$inf$
代码:
#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
#define N 2050
#define M 600050
#define inf 100000000
#define S (n*2+1)
#define T (n*2+2)
typedef long long ll;
int head[N],to[M],nxt[M],cnt=1,n,m,dep[N],Q[N],l,r;
ll flow[M],sum;
inline void add(int u,int v,ll f) {
to[++cnt]=v; nxt[cnt]=head[u]; head[u]=cnt; flow[cnt]=f;
to[++cnt]=u; nxt[cnt]=head[v]; head[v]=cnt; flow[cnt]=0;
}
bool bfs() {
memset(dep,0,sizeof(dep));
dep[S]=1; l=r=0; Q[r++]=S;
while(l<r) {
int x=Q[l++],i;
for(i=head[x];i;i=nxt[i]) {
if(!dep[to[i]]&&flow[i]) {
dep[to[i]]=dep[x]+1;
if(to[i]==T) return 1;
Q[r++]=to[i];
}
}
}
return 0;
}
ll dfs(int x,ll mf) {
if(x==T) return mf;
int i;
ll nf=0;
for(i=head[x];i;i=nxt[i]) {
if(dep[to[i]]==dep[x]+1&&flow[i]) {
ll tmp=dfs(to[i],min(mf-nf,flow[i]));
if(!tmp) dep[to[i]]=0;
nf+=tmp;
flow[i]-=tmp;
flow[i^1]+=tmp;
if(nf==mf) break;
}
}
return nf;
}
void dinic() {
ll f;
while(bfs()) while(f=dfs(S,inf)) sum-=f;
printf("%lld
",-sum);
}
int main() {
scanf("%d",&n);
int i,x,y;
for(i=1;i<=n;i++) {
scanf("%d",&x);
while(x--) {
scanf("%d",&y);
add(i,y+n,inf);
}
}
for(i=1;i<=n;i++) scanf("%d",&x),x=-x,sum+=inf+x,add(S,i,inf+x),add(i+n,T,inf);
dinic();
}