BZOJ2502:清理雪道 上下界网络流
思路:
比较一眼.
长了一个姿势,就是有源汇有上下界网络最小流求法.
首先求可行流,得到满足下界需要的流量,就是从原来的汇流回原来的源的流量(C1).
这不见得是最小的.
因此我们删去原来的源和原来的汇之间的边,再求一次从原来的汇到原来的源的最大流(C2),也即退掉尽可能多的流量.
由于下界是不会退流的.
显而易见(?).C1−C2就是答案.
据称有时候这样做还会出问题?
大家一起来围观Kanari神犇:详细的~~~~网址如下:
http://blog.csdn.net/huzecong/article/details/8631748
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 | #include<cstdio> #include<cstring> #include<cctype> #include<iostream> #include<algorithm> #include<queue> using namespace std; #define INF 0x3f3f3f3f int cnt; struct MaxflowSolver{ int head[110],next[80010],end[80010],flow[80010],ind; int d[110],gap[110],stk[110],top,cur[110]; inline void reset(){ind=0, memset (head,-1, sizeof head);} inline void addedge( int a, int b, int f){ int q=ind++;end[q]=b,next[q]=head[a],head[a]=q,flow[q]=f;} inline void make( int a, int b, int f){addedge(a,b,f),addedge(b,a,0);} inline void bfs( int T){ static int q[110]; int fr=0,ta=0; memset (d,-1, sizeof d), memset (gap,0, sizeof gap),++gap[d[T]=0],q[ta++]=T; while (fr^ta){ int i=q[fr++]; for ( int j=head[i];j!=-1;j=next[j]) if (d[end[j]]==-1)++gap[d[end[j]]=d[i]+1],q[ta++]=end[j]; } } inline int Maxflow( int S, int T){ int res=0,u=S,Min,ins,i;top=0,bfs(T), memcpy (cur,head, sizeof cur); while (d[S]<cnt+1){ if (u==T){ for (Min=INF,i=0;i<top;++i) if (flow[stk[i]]<Min)Min=flow[stk[i]],ins=i; for (res+=Min,i=0;i<top;++i)flow[stk[i]]-=Min,flow[stk[i]^1]+=Min; u=end[stk[top=ins]^1]; } if (u!=T&&!gap[d[u]-1]) break ; bool find=0; for ( int &j=cur[u];j!=-1;j=next[j]) if (flow[j]&&d[u]==d[end[j]]+1){find=1,ins=j; break ;} if (find){stk[top++]=cur[u]=ins,u=end[ins];} else { Min=cnt+1; for ( int j=head[u];j!=-1;j=next[j]) if (flow[j]&&d[end[j]]<Min)Min=d[end[j]],cur[u]=j; if (!--gap[d[u]]) break ;++gap[d[u]=Min+1]; if (u!=S)u=end[stk[--top]^1]; } } return res; } }SteinsGate; int main(){ int n; scanf ( "%d" ,&n); register int i,j; cnt=n; int SS=0,ST=++cnt,S=++cnt,T=++cnt; int t,x;SteinsGate.reset(); for (i=1;i<=n;++i){ SteinsGate.make(S,i,INF); SteinsGate.make(i,T,INF); scanf ( "%d" ,&t); while (t--) scanf ( "%d" ,&x),SteinsGate.make(SS,x,1),SteinsGate.make(i,ST,1),SteinsGate.make(i,x,INF); } SteinsGate.make(T,S,INF); int res; SteinsGate.Maxflow(SS,ST); for (j=SteinsGate.head[S];j!=-1;j=SteinsGate.next[j]) if (SteinsGate.end[j]==T)res=SteinsGate.flow[j],SteinsGate.flow[j]=SteinsGate.flow[j^1]=0; printf ( "%d" ,res-SteinsGate.Maxflow(T,S)); return 0; } |