HDOJ3585解题报告【二分答案，最大团】

题目地址：

　　http://acm.hdu.edu.cn/showproblem.php?pid=3585

题目概述：

　　给出n个点，从中选出k个，使得这个k点之间最短的距离最大，输出这个最大值。（距离即为两点之间的距离，不途经其他点）

大致思路：

　　最小值最大，最大值最小这种题可以二分答案，而判断的话用最大团的算法，只需要在加边时只加边权比当前答案大的边，只需要最大团中顶点个数大于等于k即说明当前答案满足条件。

　　其他的一些小细节见代码。

代码：

  1 #include <iostream>
  2 #include <cstdio>
  3 #include <cstdlib>
  4 #include <cmath>
  5 #include <vector>
  6 #include <ctime>
  7 #include <map>
  8 #include <set>
  9 #include <queue>
 10 #include <cstring>
 11 #include <algorithm>
 12 using namespace std;
 13 
 14 #define sacnf scanf
 15 #define scnaf scanf
 16 #define maxn 55
 17 #define maxm 26
 18 #define inf 1061109567
 19 #define Eps 0.000001
 20 const double PI=acos(-1.0);
 21 #define mod 1000000007
 22 #define MAXNUM 10000
 23 void Swap(int &a,int &b) {int t=a;a=b;b=t;}
 24 int Abs(int x) {return (x<0)?-x:x;}
 25 typedef long long ll;
 26 
 27 struct point
 28 {
 29     double x,y;
 30 } a[maxn];
 31 
 32 double f[maxn][maxn],ans[maxn*maxn];
 33 set<double> S;int vis[maxn];
 34 int num[maxn];
 35 int V[maxn][maxn],total_point=0;
 36 
 37 double dist(point a,point b) {return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));}
 38 
 39 bool dfs(int tot,int cnt,int pos,int n)
 40 {
 41     if(tot==0)
 42     {
 43         if(cnt>total_point) {total_point=cnt;return true;}
 44     }
 45     for(int i=0;i<tot;i++)
 46     {
 47         if(cnt+(tot-i)<=total_point) return false;
 48         if(cnt+num[V[cnt][i]]<=total_point) return false;
 49         int k=0;
 50         for(int j=i+1;j<tot;j++)
 51             if(f[V[cnt][i]][V[cnt][j]]>=ans[pos])
 52                 V[cnt+1][k++]=V[cnt][j];
 53         if(dfs(k,cnt+1,pos,n)) return false;
 54     }
 55     return false;
 56 }
 57 
 58 void query_max(int pos,int n)
 59 {
 60     total_point=1;
 61     for(int i=n;i>0;i--)
 62     {
 63         int k=0;
 64         for(int j=i+1;j<=n;j++)
 65         {
 66             if(f[i][j]>=ans[pos]) V[1][k++]=j;
 67         }
 68         dfs(k,1,pos,n);
 69         num[i]=total_point;
 70     }
 71 }
 72 
 73 bool judge(int pos,int n,int k)
 74 {
 75     query_max(pos,n);
 76     return total_point>=k;
 77 }
 78 
 79 int main()
 80 {
 81     //freopen("data.in","r",stdin);
 82     //freopen("data.out","w",stdout);
 83     //clock_t st=clock();
 84     int n,K;
 85     while(~scanf("%d%d",&n,&K))
 86     {
 87         for(int i=1;i<=n;i++) scanf("%lf%lf",&a[i].x,&a[i].y);
 88         for(int i=1;i<=n;i++)
 89         {
 90             f[i][i]=inf;
 91             for(int j=i+1;j<=n;j++)
 92                 f[i][j]=f[j][i]=dist(a[i],a[j]);
 93         } S.clear();
 94         for(int i=1;i<=n;i++)
 95             for(int j=1;j<=n;j++) S.insert(f[i][j]);
 96         int l=1,r=0;
 97         for(set<double>::iterator it=S.begin();it!=S.end();it++) ans[++r]=*it;
 98         r--;//for(int i=1;i<=r;i++) cout<<ans[i]<<endl;
 99         while(l<r)
100         {
101             int m=(l+r)>>1;m++;
102             if(judge(m,n,K)) l=m;
103             else r=m-1;
104         }
105         printf("%.2lf
",ans[l]);
106     }
107     //clock_t ed=clock();
108     //printf("

Time Used : %.5lf Ms.
",(double)(ed-st)/CLOCKS_PER_SEC);
109     return 0;
110 }