Description
滑雪场坐落在FJ省西北部的若干座山上。
从空中鸟瞰，滑雪场可以看作一个有向无环图，每条弧代表一个斜坡（即雪道），弧的方向代表斜坡下降的方向。
你的团队负责每周定时清理雪道。你们拥有一架直升飞机，每次飞行可以从总部带一个人降落到滑雪场的某个地点，然后再飞回总部。从降落的地点出发，这个人可以顺着斜坡向下滑行，并清理他所经过的雪道。
由于每次飞行的耗费是固定的，为了最小化耗费，你想知道如何用最少的飞行次数才能完成清理雪道的任务。
Input
输入文件的第一行包含一个整数n (2 <= n <= 100) – 代表滑雪场的地点的数量。接下来的n行，描述1~n
地点出发的斜坡，第i行的第一个数为mi (0 <= mi < n) ，后面共有mi个整数，由空格隔开，每个整数
ij互不相同，代表从地点i下降到地点aij的斜坡。每个地点至少有一个斜坡与之相连。
Output
输出文件的第一行是一个整数k – 直升飞机的最少飞行次数。
Sample Input
8
1 3
1 7
2 4 5
1 8
1 8
0
2 6 5
0
Sample Output
4
Solution
有源汇上下界最小流模板题。
对于题目给出的每条边容量范围为([1,+infty))，然后(s)向每个点连边，每个点向(t)连边，跑最小流就好了。
#include<bits/stdc++.h>
using namespace std;
void read(int &x) {
x=0;int f=1;char ch=getchar();
for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
void print(int x) {
if(x<0) putchar('-'),x=-x;
if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('
');}
const int maxn = 2e5+10;
const int inf = 1e9;
int n,a[maxn],ban[maxn];
int head[maxn],tot=1,dis[maxn];
struct edge{int to,nxt,w;}e[maxn<<1];
void add(int u,int v,int w) {e[++tot]=(edge){v,head[u],w},head[u]=tot;}
void ins(int u,int v,int w) {add(u,v,w),add(v,u,0);}
int bfs(int s,int t) {
memset(dis,-1,(n+6)*4);
queue<int > q;q.push(s);dis[s]=0;
while(!q.empty()) {
int x=q.front();q.pop();
for(int i=head[x];i;i=e[i].nxt)
if((!ban[i])&&e[i].w>0&&dis[e[i].to]==-1) {
dis[e[i].to]=dis[x]+1;
if(e[i].to==t) return 1;
q.push(e[i].to);
}
}return 0;
}
int dfs(int x,int t,int f) {
if(x==t) return f;
int used=0;
for(int i=head[x];i;i=e[i].nxt)
if(e[i].w>0&&(!ban[i])&&dis[e[i].to]==dis[x]+1) {
int d=dfs(e[i].to,t,min(f-used,e[i].w));
if(d>0) e[i].w-=d,e[i^1].w+=d,used+=d;
if(used==f) break;
}
dis[x]=-1;return used;
}
int dinic(int s,int t) {
int flow=0;
while(bfs(s,t)) flow+=dfs(s,t,inf);
return flow;
}
int main() {
read(n);
int s=n+1,t=n+2,S=n+3,T=n+4;
for(int i=1,m;i<=n;i++) {
read(m);a[i]-=m;
for(int j=1,x;j<=m;j++) read(x),a[x]++,ins(i,x,inf);
}
for(int i=1;i<=n;i++) ins(s,i,inf),ins(i,t,inf);
int x=tot+1;ins(t,s,inf);
for(int i=1;i<=n;i++)
if(a[i]>0) ins(S,i,a[i]);else ins(i,T,-a[i]);
int res=dinic(S,T);res=inf-e[x].w;
for(int i=x;i<=tot;i++) ban[i]=1;
int del=dinic(t,s);
write(res-del);
return 0;
}