有源汇有上下界的最小可行流。
YY一下建图应该很好搞吧（？
就是对于每个雪道都是[1,inf]然后源点到所有点都是[0,inf]所有点到汇点都是[0,inf]
这样的话跑一个有源汇上下界最小可行流就可以了
有关于这个可以看liu_runda神犇的介绍 非常直观易懂
最开始先建超级源汇 跑可行流得到一个基础流量 然后反向在残余网络上跑最大流减去即可
注意最后的时候是需要反向在残余网络上跑的 不要忘记交换源汇
代码。
//Love and Freedom. #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #define inf 20021225 #define ll long long #define N 200 #define M 40000 using namespace std; struct edge{int lt,to,f;}e[M<<1]; int cnt=1,in[N],dep[N],s,t,ss,tt; queue<int> q; void add(int x,int y,int f) { e[++cnt].to = y; e[cnt].lt = in[x]; in[x] = cnt; e[cnt].f = f; e[++cnt].to = x; e[cnt].lt = in[y]; in[y] = cnt; e[cnt].f = 0; } bool bfs() { while(!q.empty()) q.pop(); q.push(s); memset(dep,0,sizeof(dep)); dep[s] = 1; while(!q.empty()) { int x = q.front(); q.pop(); for(int i=in[x];i;i=e[i].lt) { int y = e[i].to; if(dep[y] || !e[i].f) continue; dep[y] = dep[x]+1; q.push(y); if(y==t) return 1; } } return 0; } int dfs(int x,int f) { if(!f || x==t) return f; int flow = f; for(int i=in[x];i;i=e[i].lt) { int y = e[i].to; if(dep[y] == dep[x]+1 && e[i].f && flow) { int cur = dfs(y,min(flow,e[i].f)); e[i^1].f += cur; e[i].f -= cur; flow -= cur; if(!flow) return f; } } dep[x] = -1; return f-flow; } int dinic() { int ans = 0; while(bfs()) ans+=dfs(s,inf); return ans; } int most[M],f[N],n; void del(int x) { for(int i=in[x];i;i=e[i].lt) e[i].f = e[i^1].f = 0; } int main() { s = N-6; t = s+1; ss = t+1; tt = ss+1; scanf("%d",&n); for(int x=1;x<=n;x++) { int i,y; scanf("%d",&i); while(i--) { scanf("%d",&y); f[y]++; f[x]--; add(x,y,inf); } } for(int x=1;x<=n;x++){add(s,x,inf); add(x,t,inf);} for(int i=1;i<=n;i++) { if(f[i]<0) add(i,tt,-f[i]); else add(ss,i,f[i]); } add(t,s,inf); int tmps = s,tmpt = t; s = ss; t = tt; int flow = dinic(); flow = e[cnt].f; e[cnt].f = e[cnt-1].f = 0; del(ss); del(tt); s = tmpt,t = tmps; printf("%d ",flow-dinic()); return 0; }