Description
SGU似乎死了... 题目搬到了Codeforces...
Problem - 99999438 - Codeforces
Solution
动态最大流.
考虑如果不求时间, 只求能否到达对岸, 这显然是一个拆点最大流.
如果加上时间的限制, 考虑按照时间拆点, 然后枚举时间 (t), 并且连上 (t) 时间能到达的点.
具体的, 设河的这一岸为 (s), 对岸为 (t). (t) 时刻的点 (p) 为 (p_t), 并拆成两个点 (p_t'), (p_t'').
对于 (t) 时刻, 连边 ((p_t', p_t'', c_p)). 对于能到达 (s) 或 (t) 的节点, 分别连边 ((s, p_t',infty)), ((p_{t-1}'', t, infty)). 对于能互相到达的点 (u, v), 连边 ((u_{t-1}, v_t, infty)), ((v_{t-1}, u_t, infty)).
那么当总最大流 (ge m) 时, 当前枚举的时间即为答案.
Code
#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<set>
#include<map>
using namespace std;
#define rep(i,l,r) for(register int i=(l);i<=(r);++i)
#define repdo(i,l,r) for(register int i=(l);i>=(r);--i)
#define il inline
typedef double db;
typedef long long ll;
//---------------------------------------
const int nsz=60,n2sz=3050,psz=14050,esz=1e6+50,ninf=1e9+7;
int n,m,d,w,pos[nsz][3],link[nsz][2];
int pow2(int v){return v*v;}
struct te0{int f,t;}e0[n2sz];
int pe0=0;
struct te{int t,pr,fl;}edge[esz*2];
int hd[psz],pe=1,ss,tt,np;
void adde(int f,int t,int fl){edge[++pe]=(te){t,hd[f],fl};hd[f]=pe;}
void addsg(int f,int t,int fl){adde(f,t,fl),adde(t,f,0);}
int cur[psz],gap[psz],dep[psz];
void init(){
rep(i,1,np)cur[i]=hd[i],gap[i]=0,dep[i]=0;
static int que[psz],qh,qt;
qh=1,qt=0;
que[++qt]=tt,gap[1]=1,dep[tt]=1;
while(qh<=qt){
int u=que[qh++];
for(int i=hd[u],v;i;i=edge[i].pr){
v=edge[i].t;
if(dep[v])continue;
dep[v]=dep[u]+1,++gap[dep[v]],que[++qt]=v;
}
}
}
int dfs(int p,int mi){
if(p==tt||mi==0)return mi;
int fl=0,tmp;
for(int &i=cur[p],v;i;i=edge[i].pr){
v=edge[i].t;
if(dep[v]+1!=dep[p])continue;
tmp=dfs(v,min(mi,edge[i].fl));
fl+=tmp,mi-=tmp,edge[i].fl-=tmp,edge[i^1].fl+=tmp;
if(mi==0)return fl;
}
if(gap[dep[p]]==1)dep[ss]=np+1;
--gap[dep[p]],++dep[p],++gap[dep[p]];
cur[p]=hd[p];
return fl;
}
int maxfl(){
init();
int res=0;
while(dep[ss]<=np)res+=dfs(ss,ninf);
return res;
}
int tr(int p,int tm,int fl){//fl==0: from; fl==1: to
return (n*(tm-1)+p)*2-1+fl;
}
int sum=0;
int sol(){
if(d>=w)return 1;
else if(n==0)return -1;
ss=(n+m+5)*n*2+1,tt=(n+m+5)*n*2+2,np=tt;
rep(tm,1,n+m+1){
rep(i,1,n)if(link[i][0])addsg(ss,tr(i,tm,0),ninf);
if(tm>1)rep(i,1,n)if(link[i][1])addsg(tr(i,tm-1,1),tt,ninf);
rep(i,1,n)addsg(tr(i,tm,0),tr(i,tm,1),pos[i][2]);
if(tm>1){
rep(i,1,pe0){
addsg(tr(e0[i].f,tm-1,1),tr(e0[i].t,tm,0),ninf);
addsg(tr(e0[i].t,tm-1,1),tr(e0[i].f,tm,0),ninf);
}
}
sum+=maxfl();
// printf("tm=%d sum=%d
",tm,sum);
if(sum>=m)return tm;
}
return -1;
}
int main(){
ios::sync_with_stdio(0),cin.tie(0);
cin>>n>>m>>d>>w;
rep(i,1,n)cin>>pos[i][0]>>pos[i][1]>>pos[i][2];
rep(i,1,n){
if(pos[i][1]<=d)link[i][0]=1;
if(pos[i][1]>=w-d)link[i][1]=1;
rep(j,i+1,n){
if(pow2(pos[i][0]-pos[j][0])+pow2(pos[i][1]-pos[j][1])<=pow2(d))e0[++pe0]=(te0){i,j};
}
}
int ans=sol();
if(ans==-1)cout<<"IMPOSSIBLE
";
else cout<<ans<<'
';
return 0;
}