BZOJ1570:[JSOI2008]Blue Mary的旅行 暴力+网络流
思路:
暴力枚举答案,然后将点分层,边总是从该层连向下一层.
然后判断最大流是不是满足题意.
具体连边看代码.
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 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 | #include<cstdio>#include<cstring>#include<cctype>#include<iostream>#include<algorithm>using namespace std; #define INF ~0U>>1struct Solver{ static const int V=50*100; static const int E=2450*100*2; int head[V],next[E],end[E],flow[E],ind; int d[V],gap[V],stk[V],top,cur[V]; inline void reset(){ ind=top=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){ /*printf("%d %d %d\n",a,b,f);*/addedge(a,b,f),addedge(b,a,0); } inline void bfs(int T){ static int q[V];int fr=0,ta=0; memset(gap,0,sizeof gap),memset(d,-1,sizeof d),++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){ bfs(T),memcpy(cur,head,sizeof cur); int re=0,Min,ins,i,u=S; while(d[S]<T-S+1){ if(u==T){ for(Min=INF,i=0;i<top;++i)if(Min>flow[stk[i]])ins=i,Min=flow[stk[i]]; for(re+=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[end[j]]+1==d[u]){ find=1,ins=j;break; } if(find){stk[top++]=cur[u]=ins,u=end[ins];} else{ Min=T-S+1; for(int j=head[u];j!=-1;j=next[j])if(flow[j]&&d[end[j]]<Min) cur[u]=j,Min=d[end[j]]; if(!--gap[d[u]])break; ++gap[d[u]=Min+1]; if(u!=S)u=end[stk[--top]^1]; } } return re; }}Stg; struct Edge{ int u,v,f;}E[2510]; #define get(x,dep) ((dep-1)*n+x)int main(){ int n,m,T;scanf("%d%d%d",&n,&m,&T); register int i,j; for(i=1;i<=m;++i)scanf("%d%d%d",&E[i].u,&E[i].v,&E[i].f); int re; for(re=1;;++re){ Stg.reset(); for(i=1;i<=m;++i)for(j=1;j<=re;++j)Stg.make(get(E[i].u,j),get(E[i].v,j+1),E[i].f); for(j=1;j<=re;++j)Stg.make(0,get(1,j),INF); for(j=2;j<=re+1;++j)Stg.make(get(n,j),n*(re+1)+1,INF); int now=Stg.Maxflow(0,n*(re+1)+1); //printf("%d\n",now); if(now>=T)break; } printf("%d\n",re); return 0;} |
评论 (0)