题目链接：https://cn.vjudge.net/contest/69431#problem/D

题意：

有一条河，河上有一些垃圾(看成点)，人借助垃圾跳到对岸，已知垃圾坐标位置，人每次最大跳跃距离，河的

宽度以及人数，问是否所有人可以跳到对岸，若可以，求出最短时间。

解法：

第一次碰到动态流，还是队友推荐来做的。 题解来自：ORZ

我们知道时间的上限是n+m，因为对于第一个人他从一河岸跳到对岸最多踩m个垃圾，加上到达对岸的一步，

共需花m+1单位的时间，而第二个人他可以在第一人跳到第二个垃圾时重复第一人的跳法，也就是后面一人

比前面一人晚到对岸1个单位时间，那么有n-1人重复此过程，因此最大时间m+1+n-1=m+n，若超过此时

间，所有人未到对岸，显然是无解情况。

对于有解情况：我们先预处理所有垃圾两两之间的距离是否小于等于D，也就是能否在这些垃圾之间跳来跳

去，麻烦的是河岸并不是一个点，而是一条线，因此我们也要预处理能从左岸（出发地）跳到的垃圾（y坐标

<=D）,和能从哪些垃圾跳到对岸（y坐标+D>=M）.

然后根据时间拆点，记i点在t时刻的状态为（i，t），这里注意t=1，就是直接从左岸跳到对岸，这个可以判断

D>=M求得，然后我们从t=2开始枚举，这里要考虑清楚，我之前建模没想明白，t-1时刻，人是站在（i，t-

1）状态上的，那么t时刻人可以从（i，t-1）跳到对岸（如果满足条件的话），也就是要将所有（i，t-1）连

向汇点，千万不要将（i，t）连向汇点，当然也可以选择从（i，t-1）跳到（j，t）（i,j距离<=D）,当然不要忘

了从左岸连向那些y坐标<=D的点（一步可达点），这样就差不多了。

最后别忘了，每个点需要拆成两个点，不这样做的话会有大量流量聚集在i点，然后通过下一时刻流出去，这

样就超过i在某一时刻最大人数限制了。此题拆点是挺麻烦的。

PS:这里最多会有10000割点左右，最坏情况有10^8条边，显然内存不允许，dinic算法也会TLE，所以可以推

断，数据显然不会出现这么多边和点的情况。所以随便开了2000000就AC。

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 15000;
const int maxm = 2000000;
const int inf = 0x3f3f3f3f;
struct G
{
    int v, cap, next;
    G() {}
    G(int v, int cap, int next) : v(v), cap(cap), next(next) {}
} E[maxm];
int p[maxn], T;
int d[maxn], temp_p[maxn], qw[maxn]; //d顶点到源点的距离标号,temp_p当前狐优化，qw队列
void init()
{
    memset(p, -1, sizeof(p));
    T = 0;
}
void add(int u, int v, int cap)
{
    E[T] = G(v, cap, p[u]);
    p[u] = T++;
    E[T] = G(u, 0, p[v]);
    p[v] = T++;
}
bool bfs(int st, int en, int n)
{
    int i, u, v, head, tail;
    for(i = 0; i <= n; i++) d[i] = -1;
    head = tail = 0;
    d[st] = 0;
    qw[tail] = st;
    while(head <= tail)
    {
        u = qw[head++];
        for(i = p[u]; i + 1; i = E[i].next)
        {
            v = E[i].v;
            if(d[v] == -1 && E[i].cap > 0)
            {
                d[v] = d[u] + 1;
                qw[++tail] = v;
            }
        }
    }
    return (d[en] != -1);
}
int dfs(int u, int en, int f)
{
    if(u == en || f == 0) return f;
    int flow = 0, temp;
    for(; temp_p[u] + 1; temp_p[u] = E[temp_p[u]].next)
    {
        G& e = E[temp_p[u]];
        if(d[u] + 1 == d[e.v])
        {
            temp = dfs(e.v, en, min(f, e.cap));
            if(temp > 0)
            {
                e.cap -= temp;
                E[temp_p[u] ^ 1].cap += temp;
                flow += temp;
                f -= temp;
                if(f == 0)  break;
            }
        }
    }
    return flow;
}
int dinic(int st, int en, int n)
{
    int i, ans = 0;
    while(bfs(st, en, n))
    {
        for(i = 0; i <= n; i++) temp_p[i] = p[i];
        ans += dfs(st, en, inf);
    }
    return ans;
}
//最大流

bool g[55][55];
int n, m, val[55], xx[55], yy[55];
int getid(int id, int t, int p)
{
    return 2*n*(t-1)+p*n+id;
}
bool check(int t){
    init();
    int source = 0, sink = 2*n*t+1;
    for(int i=1; i<=n; i++){
        for(int j=1; j<=t; j++){
            add(getid(i,j,0),getid(i,j,1),val[i]);
            if(j<t){
                add(getid(i,j,1),getid(i,j+1,0),inf);
            }
        }
    }
    for(int i=1; i<=n; i++){
        if(g[0][i]){
            for(int j=1; j<=t; j++) add(source, getid(i,j,0), inf);
        }
        if(g[i][n+1]){
            for(int j=1; j<=t; j++) add(getid(i,j,1), sink, inf);
        }
        for(int j=1; j<=n; j++){
            if(g[i][j]){
                for(int k=1; k<t; k++){
                    add(getid(i,k,1), getid(j,k+1,0), inf);
                }
            }
        }
    }
    int ans = dinic(source, sink, sink+2);
    return ans >= m;
}

int main()
{
    while(scanf("%d%d", &n,&m) != EOF)
    {
        memset(g, 0, sizeof(g));
        int d, w;
        scanf("%d%d", &d, &w);
        for(int i=1; i<=n; i++){
            scanf("%d%d%d",&xx[i],&yy[i],&val[i]);
        }
        if(w<=d){
            printf("1\n");
            continue;
        }
        for(int i=1; i<=n; i++){
            if(yy[i]<=d) g[0][i]=1;
            if(w-yy[i]<=d) g[i][n+1]=1;
            for(int j=1; j<=n; j++){
                if(i!=j){
                    if(sqrt((xx[i]-xx[j])*(xx[i]-xx[j])+(yy[i]-yy[j])*(yy[i]-yy[j])) <= d){
                        g[i][j]=g[j][i]=1;
                    }
                }
            }
        }
        int ans = -1, l=1, r=102;
        while(l <= r){
            int mid = (l+r)/2;
            if(check(mid)) ans = mid, r = mid-1;
            else l = mid+1;
        }
        if(ans == -1) printf("IMPOSSIBLE\n");
        else printf("%d\n", ans+1);
    }
    return 0;
}