首页 > 代码库 > HDU 3656 二分+dlx判定

HDU 3656 二分+dlx判定

2024-07-02 12:42:07   226人阅读

Fire station

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1308    Accepted Submission(s): 434


Problem Description
A city‘s map can be seen as a two dimensional plane. There are N houses in the city and these houses can be seen as N points P1 …… PN on the two dimensional plane. For simplicity‘s sake, assume that the time spent from one house number to another is equal to the distance between two points corresponding to the house numbers. The government decides to build M fire stations from N houses. (If a station is build in Pi, We can think the station is next to the house and the time from the station to the house is considered zero.) It is obvious that if some place such as Pi is breaking out of fire, the nearest station will dispatched a fire engine quickly rushed to the rescue scene. The time it takes from this station to the rescue scene is called rescue time. Now you need to consider about a problem that how to choice the positions of the M fire station to minimize the max rescue time of all the houses.
 

Input
The fi rst line of the input contains one integer T, where T is the number of cases. For each case, the fi rst line of each case contains two integers N and M separated by spaces (1 ≤ M ≤N ≤ 50), where N is the number of houses and M is the number of fire stations. Then N lines is following. The ith line contains two integers Xi and Yi (0 ≤ Xi, Yi ≤ 10000), which stands for the coordinate of the ith house.
 

Output
The rescue time which makes the max rescue time is minimum.
 

Sample Input
2
4 2
1 1
1 2
2 3
2 4
4 1
1 1
1 2
2 3
2 4
 

Sample Output
1.000000
2.236068
 给定n个城市，要修建m个防火站，使得每一个城市发生火灾所需要的最大救援时间最短。
一开始二分距离，然后枚举建边，dlx判定tle，学习别人的写法，把两点间距离的序列排序，二分下标，这样时效高了很多。
距离序列第二重循环只枚举一半wa，全部枚举ac，很不理解。
代码：
/* ***********************************************
Author :_rabbit
Created Time :2014/4/28 14:08:33
File Name :1.cpp
************************************************ */
#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef long long ll;
struct Point{
    double x,y;
}city[600];
double dis[600][600],dd[500100];
double dist(Point a,Point b){
    double s=a.x-b.x,t=a.y-b.y;
    return sqrt(s*s+t*t);
}
struct DLX{
    const static int maxn=311110;
    #define FF(i,A,s) for(int i = A[s];i != s;i = A[i])
    int L[maxn],R[maxn],U[maxn],D[maxn];
    int size,col[maxn],row[maxn],s[maxn],H[maxn];
    bool vis[700];
    int ans[maxn],cnt;
    void init(int m){
        for(int i=0;i<=m;i++){
            L[i]=i-1;R[i]=i+1;U[i]=D[i]=i;s[i]=0;
        }
        memset(H,-1,sizeof(H));
        L[0]=m;R[m]=0;size=m+1;
    }
    void link(int r,int c){
         U[size]=c;D[size]=D[c];U[D[c]]=size;D[c]=size;
         if(H[r]<0)H[r]=L[size]=R[size]=size;
         else {
             L[size]=H[r];R[size]=R[H[r]];
             L[R[H[r]]]=size;R[H[r]]=size;
         }
         s[c]++;col[size]=c;row[size]=r;size++;
     }
    void del(int c){//精确覆盖
        L[R[c]]=L[c];R[L[c]]=R[c];  
        FF(i,D,c)FF(j,R,i)U[D[j]]=U[j],D[U[j]]=D[j],--s[col[j]];  
    }  
    void add(int c){  //精确覆盖
        R[L[c]]=L[R[c]]=c;  
        FF(i,U,c)FF(j,L,i)++s[col[U[D[j]]=D[U[j]]=j]];  
    }  
    bool dfs(int k){//精确覆盖
        if(!R[0]){  
            cnt=k;return 1;  
        }  
        int c=R[0];FF(i,R,0)if(s[c]>s[i])c=i;  
        del(c);  
        FF(i,D,c){  
            FF(j,R,i)del(col[j]);  
            ans[k]=row[i];if(dfs(k+1))return true;  
            FF(j,L,i)add(col[j]);  
        }  
        add(c);  
        return 0;
    }  
    void remove(int c){//重复覆盖
        FF(i,D,c)L[R[i]]=L[i],R[L[i]]=R[i];
    }
     void resume(int c){//重复覆盖
         FF(i,U,c)L[R[i]]=R[L[i]]=i;
     }
    int A(){//估价函数
        int res=0;
        memset(vis,0,sizeof(vis));
        FF(i,R,0)if(!vis[i]){
                res++;vis[i]=1;
                FF(j,D,i)FF(k,R,j)vis[col[k]]=1;
            }
        return res;
    }
    void dfs(int now,int &lim){//重复覆盖  
        if(R[0]==0)cnt=now,lim=min(lim,now);
        else if(now+A()<lim){  
            int temp=INF,c;  
            FF(i,R,0)if(temp>=s[i])temp=s[i],c=i;  
            FF(i,D,c){  
                ans[now]=i;
                remove(i);FF(j,R,i)remove(j);  
                dfs(now+1,lim);  
                FF(j,L,i)resume(j);resume(i);  
            }  
        }
    }
}dlx;
int main()
{
     //freopen("data.in","r",stdin);
     //freopen("data.out","w",stdout);
     int T,n,m;
     cin>>T;
     while(T--){
         scanf("%d%d",&n,&m);
         for(int i=1;i<=n;i++)scanf("%lf%lf",&city[i].x,&city[i].y);
         int pp=0;
         for(int i=1;i<=n;i++)
             for(int j=1;j<=n;j++){
                 dis[i][j]=dist(city[i],city[j]);
                 dd[pp++]=dis[i][j];
             }
         sort(dd,dd+pp);
         int left=0,right=pp-1;
         while(left<right){
             int mid=(left+right)/2;
             dlx.init(n);
             for(int i=1;i<=n;i++)
                 for(int j=1;j<=n;j++)
                     if(dis[i][j]<=dd[mid])dlx.link(i,j);
             int ans=INF;
             dlx.dfs(0,ans);
             if(ans>m)left=mid+1;
             else right=mid;
         }
         printf("%.6lf\n",dd[left]);
     }
     return 0;
}



联系
我们