首页 > ACM题库 > HDU-杭电 > HDU 3585-maximum shortest distance-分治-[解题报告]HOJ
2014
11-27

HDU 3585-maximum shortest distance-分治-[解题报告]HOJ

maximum shortest distance

问题描述 :

There are n points in the plane. Your task is to pick k points (k>=2), and make the closest points in these k points as far as possible.

输入:

For each case, the first line contains two integers n and k. The following n lines represent n points. Each contains two integers x and y. 2<=n<=50, 2<=k<=n, 0<=x,y<10000.

输出:

For each case, the first line contains two integers n and k. The following n lines represent n points. Each contains two integers x and y. 2<=n<=50, 2<=k<=n, 0<=x,y<10000.

样例输入:

3 2
0 0
10 0
0 20

样例输出:

22.36

    这道题是学习了最大团过程中遇到的一道题目,最大团学习中的体会就是搜索的基本功还是不扎实,最大团是一个NP完全问题(不懂装懂了),现在还没多项式算法,只能靠启发式搜索或者是回溯来实现了。回溯法也可以通过各种剪枝来优化。

    回到这道题目,意思就是给定平面上一些点,求出K个点满足其实每个点的距离都大于M,求M.

    通过不断的二分距离,如果距离大于二分出来的距离,那么就建边,求出最大团,就是满足距离大于M的最大个数,然后就是无限TLE。因为我是通过直接二分它们之间的距离,但是这道题目的特殊性就在于,最终二分出来的值必定是某两个点之间的距离,我们具体在操作的时候相当于可以直接离散化,把所有的距离预处理出来,然后直接对这些个别距离进行二分。终于700ms+水过了。。。这个方法感觉非常实用的一个小技巧maximum shortest distance。继续加油

 

 

#include<stdio.h>
#include<math.h>
#include<iostream>
#define eps 1e-7
using namespace std;

int n,k,vis[55],tmax,dp[55],ji;
int locat[55][2],map[55][55];
double dis[55][55],distan[2000];

int cmp(const void *a,const void*b)
{
    return *(double *)a>*(double *)b?1:-1;
}

void build(int mid)
{
    int i,f;
    for(i=1;i<=n;i++)
    {
        for(f=1;f<=n;f++)
        {
            if(dis[i][f] >= distan[mid]-eps)
            {
                map[i][f]=1;
            }
            else
            {
                map[i][f]=0;
            }
        }
        map[i][i]=0;
    }
}

void dfs(int id,int cnt)
{
    int tvis[55],i,f,able=0;
    for(i=id+1;i<=n;i++)
    {
        if(1 == vis[i])
        {
            able++;
        }    
    }
    if(0 == able)
    {
        tmax=max(tmax,cnt);
    }    
    if(cnt + able <= tmax)
    {
        return ;
    }
    for(i=1;i<=n;i++)
    {
        tvis[i]=vis[i];
    }
    for(i=id+1;i<=n;i++)
    {
        if(0 == tvis[i])
        {
            continue;    
        }
        if(cnt +dp[i] <= tmax)
        {
            continue;    
        }
        for(f=id+1;f<=n;f++)
        {
            vis[f]=tvis[f]&map[i][f];
        }
        dfs(i,cnt+1);
    }
}

int max_clique()
{
    int i,f;
    tmax=1;
    dp[n]=1;
    for(i=n-1;i>=1;i--)
    {
        for(f=1;f<=n;f++)
        {
            vis[f]=map[i][f];
        }    
        dfs(i,1);
        dp[i]=tmax;
        if(n == tmax)
        {
            return tmax;
        }
    }
    return tmax;
}

double bs()
{
    int l=0,r=ji,mid;
    while(l != r-1)
    {
        mid=(l+r)>>1;    
        build(mid);        
        if(k <= max_clique())
        {
            l=mid;
        }
        else
        {
            r=mid;
        }
    } 
    return distan[l];
}

int main()
{
    int i,f,g,sum;
    while(scanf("%d%d",&n,&k)!=EOF)
    {
        ji=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d%d",&locat[i][0],&locat[i][1]);
        }
        for(i=1;i<=n;i++)
        {
            for(f=1;f<=n;f++)
            {
                sum=0;
                for(g=0;g<2;g++)
                {
                    sum+=(locat[i][g]-locat[f][g])*((locat[i][g]-locat[f][g]));
                }
                dis[i][f]=sqrt((double)sum);
                if(i > f)
                {
                    distan[ji]=dis[i][f];
                    ji++;
                }
            }
        }
        qsort(distan,ji,sizeof(distan[0]),cmp);        
        printf("%.2lf\n",bs());
    }
    return 0;
}

 

参考:http://blog.csdn.net/qq564690377/article/details/7983972


  1. FINE有名詞罰款的意思,be fined的話就笑不出來了。 第一眼遠處看下去就看見FINE,就是罰款,車主多多少少都會經歷一下mini heart attack,然後才看到”don’t worry you wi

  2. FINE有名詞罰款的意思,be fined的話就笑不出來了。 第一眼遠處看下去就看見FINE,就是罰款,車主多多少少都會經歷一下mini heart attack,然後才看到”don’t worry you wi

  3. FINE有名詞罰款的意思,be fined的話就笑不出來了。 第一眼遠處看下去就看見FINE,就是罰款,車主多多少少都會經歷一下mini heart attack,然後才看到”don’t worry you wi

  4. FINE有名詞罰款的意思,be fined的話就笑不出來了。 第一眼遠處看下去就看見FINE,就是罰款,車主多多少少都會經歷一下mini heart attack,然後才看到”don’t worry you wi

  5. FINE有名詞罰款的意思,be fined的話就笑不出來了。 第一眼遠處看下去就看見FINE,就是罰款,車主多多少少都會經歷一下mini heart attack,然後才看到”don’t worry you wi

  6. FINE有名詞罰款的意思,be fined的話就笑不出來了。 第一眼遠處看下去就看見FINE,就是罰款,車主多多少少都會經歷一下mini heart attack,然後才看到”don’t worry you wi

  7. FINE有名詞罰款的意思,be fined的話就笑不出來了。 第一眼遠處看下去就看見FINE,就是罰款,車主多多少少都會經歷一下mini heart attack,然後才看到”don’t worry you wi

  8. 第一句可以忽略不计了吧。从第二句开始分析,说明这个花色下的所有牌都会在其它里面出现,那么还剩下♠️和♦️。第三句,可以排除2和7,因为在两种花色里有。现在是第四句,因为♠️还剩下多个,只有是♦️B才能知道答案。

  9. 思路二可以用一个长度为k的队列来实现,入队后判断下队尾元素的next指针是否为空,若为空,则出队指针即为所求。