首页 > 代码库 > SGU438_The Glorious Karlutka River =)
SGU438_The Glorious Karlutka River =)
好题，有一些人在河的一边，想通过河里的某些点跳到对岸去。每个点最多只能承受一定数量的人，每人跳跃一次需要消耗一个时间。求所有人都过河的最短时间。
看网上说是用了什么动态流的神奇东东。其实就是最大流吧，不过是一个很有意思的模型。
每递增一个时间，所有的点增加一层，因为有的人可以站在上一个点不走动，最终每个点分别表示河中的某个点在某个特定的时刻。
同时为了保证人数在点的承受范围之内，拆点即可。
一直增加层数，直到最大流达到m为止即可。
召唤代码君：
#include <iostream>#include <cstdio>#include <cstring>#define maxn 55555#define maxm 9999999using namespace std;int to[maxm],next[maxm],c[maxm],first[maxn],edge;int Q[maxm],bot,top,node;int tag[maxn],d[maxn],TAG=520;int L[55],R[55];bool can[maxn],iq[maxn];int X[55],Y[55],C[55],connect[55][55];int n,m,D,W,s,t,ans;int addnode(){ first[++node]=-1; return node;}void addedge(int U,int V,int W){ edge++; to[edge]=V,c[edge]=W,next[edge]=first[U],first[U]=edge; edge++; to[edge]=U,c[edge]=0,next[edge]=first[V],first[V]=edge;}bool _input(){ bot=1,top=0; scanf("%d%d%d%d",&n,&m,&D,&W); for (int i=1; i<=n; i++) { iq[i]=false; scanf("%d%d%d",&X[i],&Y[i],&C[i]); if (C[i]==0) { i--,n--; continue; } if (Y[i]<=D) Q[++top]=i,iq[i]=true; } memset(connect,false,sizeof connect); for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) if (i!=j && (X[i]-X[j])*(X[i]-X[j])+(Y[i]-Y[j])*(Y[i]-Y[j])<=D*D) connect[i][j]=connect[j][i]=true; while (bot<=top) { int cur=Q[bot++]; if (Y[cur]+D>=W) return true; for (int i=1; i<=n; i++) if (connect[cur][i] && !iq[i]) Q[++top]=i,iq[i]=true; } if (D<W) return false; else return true;}void build_init_graph(){ edge=-1,node=0; s=addnode(),t=addnode(); for (int i=1; i<=n; i++) L[i]=addnode(),R[i]=addnode(); for (int i=1; i<=n; i++) { addedge(L[i],R[i],C[i]); if (Y[i]<=D) addedge(s,L[i],C[i]); if (Y[i]+D>=W) addedge(R[i],t,C[i]); }}bool bfs(){ Q[bot=top=1]=t,d[t]=0,tag[t]=++TAG,can[t]=false; while (bot<=top) { int cur=Q[bot++]; for (int i=first[cur]; i!=-1; i=next[i]) if (c[i^1]>0 && tag[to[i]]!=TAG) { tag[to[i]]=TAG,d[to[i]]=d[cur]+1; can[to[i]]=false,Q[++top]=to[i]; if (to[i]==s) return true; } } return false;}int dfs(int cur,int num){ if (cur==t) return num; int tmp=num,k; for (int i=first[cur]; i!=-1; i=next[i]) if (c[i]>0 && d[to[i]]==d[cur]-1 && tag[to[i]]==TAG && !can[to[i]]) { k=dfs(to[i],min(num,c[i])); if (k) num-=k,c[i]-=k,c[i^1]+=k; if (num==0) break; } if (num) can[cur]=true; return tmp-num;}int maxflow(){ int tot=0; while (bfs()) tot+=dfs(s,maxm); return tot;}int main(){ if (!_input()) { puts("IMPOSSIBLE"); return 0; } if (D>=W) { puts("1"); return 0; } build_init_graph(); for (ans=2; maxflow()<m; ans++) { for (int i=1; i<=edge; i+=2) if (c[i]>0) c[i-1]+=c[i],c[i]=0; for (int i=1; i<=n; i++) { L[i]=addnode(); if (Y[i]<=D) addedge(s,L[i],C[i]); for (int j=1; j<=n; j++) if (connect[i][j]) addedge(R[j],L[i],C[i]); } for (int i=1; i<=n; i++) { R[i]=addnode(); addedge(L[i],R[i],C[i]); if (Y[i]+D>=W) addedge(R[i],t,C[i]); } } printf("%d\n",ans); return 0;}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。