上下界网络流入门题...
每条边有一个下界流量 $1$，没有上界，求最小流
直接上下界最小流模板套进去就好了...
#include#include #include #include #include #include using namespace std;typedef long long ll;inline int read(){ int x=0,f=1; char ch=getchar(); while(ch<'0'||ch>'9') { if(ch=='-') f=-1; ch=getchar(); } while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+(ch^48); ch=getchar(); } return x*f;}const int N=1e5+7,M=4e6+7,INF=1e9+7;int fir[N],from[M],to[M],val[M],cntt=1;inline void add(int a,int b,int c){ from[++cntt]=fir[a]; fir[a]=cntt; to[cntt]=b; val[cntt]=c; from[++cntt]=fir[b]; fir[b]=cntt; to[cntt]=a; val[cntt]=0;}int n,SS,TT,sumflow[N],Ans;int dep[N],Fir[N],S,T;queue q;bool BFS(){ for(int i=0;i<=n+3;i++) Fir[i]=fir[i],dep[i]=0; q.push(S); dep[S]=1; int x; while(!q.empty()) { x=q.front(); q.pop(); for(int i=fir[x];i;i=from[i]) { int &v=to[i]; if(dep[v]||!val[i]) continue; dep[v]=dep[x]+1; q.push(v); } } return dep[T]>0;}int DFS(int x,int mxf){ if(x==T||!mxf) return mxf; int fl=0,res; for(int &i=Fir[x];i;i=from[i]) { int &v=to[i]; if(dep[v]!=dep[x]+1||!val[i]) continue; if( res=DFS(v,min(mxf,val[i])) ) { mxf-=res; fl+=res; val[i]-=res; val[i^1]+=res; if(!mxf) break; } } return fl;}inline int Dinic() { int res=0; while(BFS()) res+=DFS(S,INF); return res; }inline void del(int x) { for(int i=fir[x];i;i=from[i]) val[i]=val[i^1]=0; }int main(){ n=read(); int a,b; S=0,T=n+1,SS=T+1,TT=SS+1; for(int i=1;i<=n;i++) { a=read(); for(int j=1;j<=a;j++) { b=read(),add(i,b,INF); sumflow[i]--; sumflow[b]++; } add(S,i,INF); add(i,T,INF); } for(int i=1;i<=n;i++) { if(!sumflow[i]) continue; if(sumflow[i]<0) add(i,TT,-sumflow[i]); else add(SS,i,sumflow[i]); } add(T,S,INF); int tmpS=S,tmpT=T; S=SS,T=TT; Dinic(); Ans=val[cntt]; val[cntt]=val[cntt^1]=0; del(SS),del(TT); S=tmpT,T=tmpS; printf("%d",Ans-Dinic()); return 0;}