題目大意：河中有一些漂浮物，每個漂浮物有一個容量。求m個人過河的最短時間。
題目思路：經典題目,加上時間限定條件,並且容量在點上,需要拆點,假設答案時間是T,那麼每個點都要拆成2*T個點具體建法:S->SS為人數,SS->V無窮,UT,1->UT,2為點的容量,UT-1,2->VT,1無窮,UT-1,2->UT,1無窮,UT-1,2->T無窮效率關鍵是看怎麼建圖個方案和答案T的枚舉,我用了四個方法,時間效率比較如下:sap(鄰接表)按時間從小到大遍歷,每次都重新建圖重新增廣2173MSsap(鄰接表)二分時間,每次都重新建圖重新增廣409MSEK(鄰接表)按時間從小到大,但是每次增加2*n個點後在原來的基礎上增廣47MSsap(鄰接表)按時間從小到大,但是每次增加2*n個點後在原來的基礎上增廣(但是dis和gap初始化)772MS(這裡sap比EK還慢,也許是因為每次推的時候dis和gap清空了(不初始化的話答案不出來),所以推的很慢,不知道有沒有更好的算法)（以上思路摘自網上）
開始的時候我想到的就是拆點加二分，不敢確定，還是看了題解，看到題解有這總方法，試了一下，一直tle,於是還是只能用逐步加點的方式了，用dinic的模板過了。
[cpp]
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<string>
#include<queue>
#include<algorithm>
#include<vector>
#include<stack>
#include<list>
#include<iostream>
#include<map>
#include<math.h>
using namespace std;
#define inf 0x3f3f3f3f
#define Max 55555
int max(int a,int b)
{
return a>b?a:b;
}
int min(int a,int b)
{
return a<b?a:b;
}
int x[100],y[100],c[100],m,n,d,w;
int dis[Max],p[Max];
int src,dest,eid,ans;
int q[Max];
struct node
{
int to,c,next;
}e[2222222];
void addedge(int u,int v,int c)
{
e[eid]=(node){v,c,p[u]};
p[u]=eid++;
e[eid]=(node){u,0,p[v]};
p[v]=eid++;
}
int bfs()
{
int i,u,v,head=0,tail=0;
for(i=0;i<=dest+1;i++) dis[i]=0;
dis[src]=1;
q[tail++]=src;
while(head<tail)
{
u=q[head++];
for(i=p[u];~i;i=e[i].next)
if(e[i].c&&dis[v=e[i].to]==0)
{
dis[v]=dis[u]+1;
if(v==dest)
return 1;
q[tail++]=v;
}
}
return 0;
}
int dfs(int u,int limit)
{
if(u==dest)
return limit;
int v,tmp,cost=0;
for(int i=p[u];~i;i=e[i].next)
if(e[i].c&&dis[u]+1==dis[v=e[i].to])
{
tmp=dfs(v,min(limit-cost,e[i].c));
if(tmp)
{
e[i].c-=tmp;
e[i^1].c+=tmp;
cost+=tmp;
}
else
dis[v]=-1;
}
return cost;
}
int Dinic()
{
while(bfs())
ans+=dfs(src,inf);
return ans;
}
bool find(int u)
{
int i;
dis[u]=1;
if(w-y[u]<=d)
{
dis[n+1]=1;
return true;
}
for(i=1;i<=n;i++)
{
if(!dis[i]&&((x[u]-x[i])*(x[u]-x[i])+(y[u]-y[i])*(y[u]-y[i]))<=d*d)
{
if(find(i))
return true;
}
}
return false;
}
int main()
{
int i,j,k;
while(scanf("%d%d%d%d",&n,&m,&d,&w)!=EOF)
{
int cnt=0;
for(i=1;i<=n;i++)
{
scanf("%d%d%d",&x[i],&y[i],&c[i]);
if(c[i]>0)
{
x[++cnt]=x[i];
y[cnt]=y[i];
c[cnt]=c[i];
}
}
n=cnt;
if(d>=w)
{
printf("1\n");
continue;
}
for(i=0;i<=n+1;i++) dis[i]=0;
for(i=1;i<=n;i++)
{
if(!dis[i]&&y[i]<=d)
{
if(find(i)) break;
}
}
if(dis[n+1]==0)
{
puts("IMPOSSIBLE");
continue;
}
memset(p,-1,sizeof(p));
eid=0;
ans=0; www.2cto.com
src=0;dest=2*(n+m+2)*n+1;
for(k=1;k<=n+m+2;k++)
{
for(i=1;i<=n;i++)
{
if(y[i]<=d)
addedge(0,(2*k-2)*n+i,inf);
if(w-y[i]<=d)
addedge((2*k-1)*n+i,dest,inf);
addedge((2*k-2)*n+i,(2*k-1)*n+i,c[i]);
}
if(k>1)
{
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
{
if((x[i]-x[j])*(x[i]-x[j])+(y[i]-y[j])*(y[i]-y[j])<=d*d&&i!=j)
addedge((2*k-3)*n+i,(2*k-2)*n+j,inf);
}
}
if(Dinic()>=m) break;
}
printf("%d\n",k+1);
}
}
