好题，有一些人在河的一边，想通过河里的某些点跳到对岸去。每个点最多只能承受一定数量的人，每人跳跃一次需要消耗一个时间。求所有人都过河的最短时间。

看网上说是用了什么动态流的神奇东东。其实就是最大流吧，不过是一个很有意思的模型。

每递增一个时间，所有的点增加一层，因为有的人可以站在上一个点不走动，最终每个点分别表示河中的某个点在某个特定的时刻。

同时为了保证人数在点的承受范围之内，拆点即可。

一直增加层数，直到最大流达到m为止即可。

 

 

召唤代码君：

 

 

#include 
     
      #include 
      
       #include 
       
        #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) 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()
         
          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;}