学步园

A group of M tourists are walking along the Karlutka river. They want to cross the river, but they couldn't find a bridge. Fortunately, there are some piles of rubbish floating in the water, and the tourists have decided to try to cross the
river by jumping from one pile to another.

A tourist can move up to D meters in any direction at one jump. One jump takes exactly one second. tourists know that the river isW meters wide, and they have estimated the coordinates of rubbish piles (X_i, Y_i)
and the capacity of each pile (C_i, the maximum number of tourists that this pile can hold at the same time). Rubbish piles are not very large and can be represented as points. The river flows along the X axis. tourists
start on the river bank at 0 by Y axis. The Y coordinate of the opposite bank is W.

tourists would like to know if they can get to the opposite bank of the river, and how long it will take.

First line of input consists of four integers: number of rubbish piles N (0 ≤ N ≤ 50), number of tourists M (0 < M ≤ 50), maximum length of tourist's jump D (0 ≤ D ≤ 1000), and width of
the river W (0 < W ≤ 1000) Following N lines describe the rubbish piles, each line consists of three integers: (0 < X_i < 1000, 0 < Y_i < W, 0 ≤ C_i ≤
1000) — pile coordinates and capacity.

Output a single number indicating the minimal time (in seconds) in which all tourists will be able to cross the river, or the line "IMPOSSIBLE" if it is impossible to cross the river.

sample input

sample output

3 10 3 7
0 2 2
4 2 2
2 4 3

6

sample input

sample output

3 10 3 8
0 2 2
4 2 2
2 4 3

IMPOSSIBLE

分析：这题与hdu1733 Escape类似，关键在建图时不只第一个时间可以连接源点，对于每一层都必须连上源点，而且第一层不能一开始连上汇点，而应等下一层出现再连上汇点，详细构图见http://hi.baidu.com/fp_h/blog/item/f381e1df6c747c2e5982dd94.html

题目链接：http://acm.sgu.ru/problem.php?contest=0&problem=438

这个oj爆内存同样给了个tle。。。注意容量为0的点要删掉

代码：

#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
const int mm=2222222;
const int mn=55555;
const int oo=1000000000;
int node,src,dest,edge,ret,ans;
int reach[mm],flow[mm],next[mm];
int head[mn],work[mn],dis[mn],q[mn];
int x[mn],y[mn],c[mn];
bool vis[55],get[55][55];
int i,j,k,m,n,w,d;
inline int min(int a,int b)
{
    return a<b?a:b;
}
inline void addedge(int u,int v,int c)
{
    reach[edge]=v,flow[edge]=c,next[edge]=head[u],head[u]=edge++;
    reach[edge]=u,flow[edge]=0,next[edge]=head[v],head[v]=edge++;
}
inline void makegraph(int cc,int add)
{
    int i,j,w=node-2;
    while(add--)head[node++]=-1;
    for(i=2;i<=n+1;++i)
    {
        addedge(w+i,w+i+n,c[i]);
        if(get[src][i])addedge(src,w+i,oo);
        if(cc)
        {
            if(get[i][dest])addedge(w+i-n,dest,oo);
            addedge(w+i-n,w+i,oo);
            for(j=2;j<=n+1;++j)
                if(i!=j&&get[i][j])
                    addedge(w+i-n,w+j,oo);
        }
    }
}
bool Dinic_bfs()
{
    int i,u,v,l,r=0;
    for(i=0; i<node; ++i)dis[i]=-1;
    dis[q[r++]=src]=0;
    for(l=0; l<r; ++l)
        for(i=head[u=q[l]]; i>=0; i=next[i])
            if(flow[i]&&dis[v=reach[i]]<0)
            {
                dis[q[r++]=v]=dis[u]+1;
                if(v==dest)return 1;
            }
    return 0;
}
int Dinic_dfs(int u,int exp)
{
    if(u==dest)return exp;
    for(int &i=work[u],v,tmp; i>=0; i=next[i])
        if(flow[i]&&dis[v=reach[i]]==dis[u]+1&&(tmp=Dinic_dfs(v,min(exp,flow[i])))>0)
        {
            flow[i]-=tmp;
            flow[i^1]+=tmp;
            return tmp;
        }
    return 0;
}
int Dinic_flow()
{
    int i,delta;
    while(Dinic_bfs())
    {
        for(i=0; i<node; ++i)work[i]=head[i];
        while(delta=Dinic_dfs(src,oo))ret+=delta;
    }
    return ret;
}
void dfs(int i)
{
    vis[i]=1;
    for(int j=0;j<=n+1;++j)
        if(!vis[j]&&get[i][j])dfs(j);
}
bool tryit(int x1,int y1,int x2,int y2)
{
    return sqrt(double(x1-x2)*(x1-x2)+double(y1-y2)*(y1-y2))<=d;
}
int main()
{
    while(scanf("%d%d%d%d",&n,&m,&d,&w)!=-1)
    {
        memset(get,0,sizeof(get));
        for(i=1,j=2; i<=n; ++i)
        {
            scanf("%d%d%d",&x[j],&y[j],&c[j]);
            if(c[j])++j;
        }
        n=j-1-(c[j]==0);
        for(i=2; i<=n+1; ++i)
        {
            get[0][i]=get[i][0]=y[i]<=d;
            get[1][i]=get[i][1]=w-y[i]<=d;
            for(j=i+1; j<=n+1; ++j)get[j][i]=get[i][j]=tryit(x[i],y[i],x[j],y[j]);
        }
        get[0][1]=get[1][0]=w<=d;
        if(w<=d)
        {
            printf("1\n");
            continue;
        }
        for(i=0;i<=n+1;++i)vis[i]=0;
        dfs(0);
        if(!vis[1])
        {
            printf("IMPOSSIBLE\n");
            continue;
        }
        node=2,edge=ret=src=0,ans=dest=1;
        head[0]=head[1]=-1;
        makegraph(0,n*2);
        while(Dinic_flow()<m)++ans,makegraph(1,n*2);
        printf("%d\n",ans);
    }
    return 0;
}