題意： 有一條東西向流淌的河,寬為 W,河中有 N 塊石頭,每塊石頭的坐標(Xi, Yi)和最大承受人數 Ci 已知。現在有 M 個游客在河的南岸,他們想穿越這條河流,但是每個人每次最遠只能跳 D 米,每跳一次耗時 1 秒。問他們能否全部穿越這條河流,如果能,最少需要多長時間。 <= N <= 50, 0 < M <= 50, 0 <= D <= 1000, 0 < W(0<= 1000, 0 < Xi < 1000, 0 < Yi < W, 0 <= Ci <= 1000)。剛看完這題，想當然的認為它是一道最小費用流問題。但是當WA之後我才明白，這題並不是去求一個給定網絡的最大流，而是計算這個網絡隨著時間推移每次能夠留出多少流量。我們通過枚舉時間的方式來決定在什麼時刻能夠把所有的人全部送到對岸。注意人是可以從河這岸的任意x坐標出發的。 （開始人都在X軸上.對岸可以看為 Y = W的一條直線） 思路; 由於本題中 人可以站在石頭上不動 所以不能用最小費用流做 我們把每個時間點構建一層圖 把同一點的前一層和後一層相連接表示在同一個點 從t秒的時候站到了t+1秒 沒有動 如果i可以通過1秒之後到達j 則第k層的i和第k+1層的j連邊 k+1為我們判定的時間即我們假設的最大的時間 我們可以用二分法給它分配時間 也可以暴力一點點的加時間 如果點很多可以暴力加時間 源點匯點 怎麼加邊 就不用多說了 看代碼注釋
#include <cstdio>
#include <cstring>
#include <iostream>
#include <cmath>
using namespace std;
const int maxn=200*55;
const int inf=0x7fffffff;
struct node{
int v,next;
int val;
} s[maxn*200];
int level[maxn],p[maxn],que[maxn*200],out[maxn],ind;
inline void insert(int x,int y,int z){
s[ind].v=y;
s[ind].val=z;
s[ind].next=p[x];
p[x]=ind++;
s[ind].v=x;
s[ind].val=0;
s[ind].next=p[y];
p[y]=ind++;
}
void build_level(int n,int source){
int h=0,r=0,i,u;
for(i=0;i<=n; i++)level[i]=0;
level[source]=1;
que[0]=source;
while(h<=r){
u=que[h++];
for(i=p[u]; i!=-1; i=s[i].next)
{
if(s[i].val&&level[s[i].v]==0)
{
que[++r]=s[i].v;
level[s[i].v]=level[u]+1;
}
}
}
}
long dinic(long n,long source,long sink){
long ret=0,i;
while(1){
build_level(n,source);
if(level[sink]==0)break;
for(i=0; i<=n; ++i)out[i]=p[i];//有一次寫錯了'='，結果tle，調試了好久
long q=-1;
while(1){
if(q<0){//空棧中，壓入source（如果source的臨接邊沒有滿流）
for(i=out[source];i!=-1; i=s[i].next){
if(s[i].val&&out[s[i].v]!=-1&&level[s[i].v]==2)break;
}
if(i!=-1){
que[++q]=i;
out[source]=s[i].next;
}
else break;
}
long u=s[que[q]].v;
if(u==sink){
long dd=inf;
for(i=0; i<=q; i++){
if(dd>s[que[i]].val)dd=s[que[i]].val;
}
ret+=dd;
for(i=0; i<=q; i++){
s[que[i]].val-=dd;
s[que[i]^1].val+=dd;
}
for(i=0; i<=q; i++){//堵塞點
if(s[que[i]].val==0){
q=i-1;
break;
}
}
}
else{
for(i=out[u]; i!=-1; i=s[i].next){
if(s[i].val&&out[s[i].v]!=-1&&level[u]+1==level[s[i].v])break;
}
if(i!=-1){
que[++q]=i;
out[u]=s[i].next;
}
else{//當前點沒有臨接的可行流
out[u]=-1;
q--;
}
}
}
}
return ret;
}
void ini(){
ind=0;
memset(p,-1,sizeof(p));
}
int dis[55][55];
int pile[55][3];
int GetDis(int x1,int y1,int x2,int y2){
int t1=x1-x2;
int t2=y1-y2;
return t1*t1+t2*t2;
}
void Build(int n,int m,int mid,int D,int W){
ini();
//0-->超級源點;
//2*n*mid+1--->源點;
//2*n*mid+2-->匯點;
//超級源點到匯點的容量限制為最大m
insert(0,2*n*mid+1,m);
for(int k=0;k<mid;k++){
for(int i=1;i<=n;i++){
insert(2*k*n+i,2*k*n+n+i,pile[i][2]);//同一點的前一層和後一層相連接
//源點和二分圖的A部
if(pile[i][1]<=D)insert(2*n*mid+1,2*k*n+i,inf);//源點到每層的第i個點連接
//二分圖的B部到匯點
if(pile[i][1]+D>=W)insert(2*k*n+n+i,2*n*mid+2,inf);//每層的第i個點到匯點連接
}
}
//二分圖A部的點i可以到B部的點j
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(dis[i][j]<=D*D){
for(int k=0;k<mid-1;k++){
insert(2*k*n+n+i,2*(k+1)*n+j,inf);
//如果i可以通過1秒之後到達j 則第k層的i和第k+1層的j連邊
}
}
}
}
}
int main(){
int m,n,D,W;
while (scanf("%d%d%d%d",&n,&m,&D,&W)!=EOF){
ini();
for(int i=1;i<=n;i++)scanf("%d%d%d",&pile[i][0],&pile[i][1],&pile[i][2]);
if(D>=W){
printf("1\n");
continue;
}
for(int i=1;i<=n;i++){
for(int j=1;j<=i;j++){
dis[j][i]=dis[i][j]=GetDis(pile[i][0],pile[i][1],pile[j][0],pile[j][1]);
}
}
int left=1,right=m+n+1;
int ans=m+1+n;
while(left<=right){
int mid=(left+right)/2;
if(mid<=0)break;
Build(n,m,mid-1,D,W);
int t=dinic(2*n*(mid-1)+2,0,2*n*(mid-1)+2);
if(t==m)right=mid-1,ans=mid;
else left=mid+1;
}
if(ans<=m+n)printf("%d\n",ans);
else printf("IMPOSSIBLE\n");
}
return 0;
}
