Codeforces 164 D Minimum Diameter

题目链接~~>

做题感悟：越来越感觉CF的题很好，很有深度。

解题思路：

                 这题需要注意 k 的大小，因为 k 只有 30 个，最终形成的点的直径一定是某个确定的值，所以我们可以枚举这个值，然后把大于这个值的边都取消（删除不大于k 个点），这样不断二分剩下点的最小直径，每次二分的时候判断是否合法。这里判断是否合法很重要，因为这需要用dfs去枚举，一不小心就会超时。dfs 在枚举删除每个点的时候主要枚举两个方面，（1）如果想删除与当前点相连的所有边，可以选择删除所有与之相连的点 （2）可以单独删除此点，然后与之相连的所有边都删除了。这里有一个剪枝：如果下面删除所达到的状态不如上面的优就不继续深搜下去了。因为到达当前点所形成的状态是一样的（都把与1 ~ x 节点相连的边都删除了），就看剩下可以删除点多的必定优。

代码：

  

   

    

     

    
    

     

      #include<iostream>
     
    
   

    

     

    
    

     

      #include<sstream>
     
    
   

    

     

    
    

     

      #include<map>
     
    
   

    

     

    
    

     

      #include<cmath>
     
    
   

    

     

    
    

     

      #include<fstream>
     
    
   

    

     

    
    

     

      #include<queue>
     
    
   

    

     

    
    

     

      #include<vector>
     
    
   

    

     

    
    

     

      #include<sstream>
     
    
   

    

     

    
    

     

      #include<cstring>
     
    
   

    

     

    
    

     

      #include<cstdio>
     
    
   

    

     

    
    

     

      #include<stack>
     
    
   

    

     

    
    

     

      #include<bitset>
     
    
   

    

     

    
    

     

      #include<ctime>
     
    
   

    

     

    
    

     

      #include<string>
     
    
   

    

     

    
    

     

      #include<cctype>
     
    
   

    

     

    
    

     

      #include<iomanip>
     
    
   

    

     

    
    

     

      #include<algorithm>
     
    
   

    

     

    
    

     

      using namespace std  ;
     
    
   

    

     

    
    

     

      #define INT __int64
     
    
   

    

     

    
    

     

      #define L(x) (x * 2)
     
    
   

    

     

    
    

     

      #define R(x) (x * 2 + 1)
     
    
   

    

     

    
    

     

      const int INF = 0x3f3f3f3f ;
     
    
   

    

     

    
    

     

      const double esp = 0.0000000001 ;
     
    
   

    

     

    
    

     

      const double PI = acos(-1.0) ;
     
    
   

    

     

    
    

     

      const int mod = 1e9 + 7 ;
     
    
   

    

     

    
    

     

      const int MY = 1400 + 5 ;
     
    
   

    

     

    
    

     

      const int MX = 1010 + 5 ;
     
    
   

    

     

    
    

     

      int num ,n ,k ;
     
    
   

    

     

    
    

     

      vector<int>G[MX] ;
     
    
   

    

     

    
    

     

      int d[MX*MX] ,g[MX][MX] ,vis[MX] ;
     
    
   

    

     

    
    

     

      struct node
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int x ,y ;
     
    
   

    

     

    
    

     

      }P[MX] ;
     
    
   

    

     

    
    

     

      bool dfs(int cnt ,int m) // cnt 代表编号 ，m 代表删除的边数
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 if(cnt > n) return true ;
     
    
   

    

     

    
    

     
 if(vis[cnt]) return dfs(cnt + 1 ,m) ;
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < (int)G[cnt].size() ; ++i)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       m += !vis[G[cnt][i]] ;
     
    
   

    

     

    
    

     

       vis[G[cnt][i]]++ ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(m <= k && dfs(cnt + 1 ,m))
     
    
   

    

     

    
    

     
 return true ;
     
    
   

    

     

    
    

     
 int temp = m ;
     
    
   

    

     

    
    

     
 for(int i = 0 ;i < (int)G[cnt].size() ; ++i)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       vis[G[cnt][i]]-- ;
     
    
   

    

     

    
    

     

       m -= !vis[G[cnt][i]] ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 if(G[cnt].size() != 1)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       vis[cnt]++ ;
     
    
   

    

     

    
    

     
 if(m + 1 <= k && m + 1 < temp && dfs(cnt+1 ,m+1))
     
    
   

    

     

    
    

     
 return  true ;
     
    
   

    

     

    
    

     

       vis[cnt]-- ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return false ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      bool judge(int dist)
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 memset(vis ,false ,sizeof(vis)) ;
     
    
   

    

     

    
    

     
 for(int i = 1 ;i <= n ; ++i)
     
    
   

    

     

    
    

     

       G[i].clear() ;
     
    
   

    

     

    
    

     
 for(int i = 1 ;i < n ; ++i)
     
    
   

    

     

    
    

     
 for(int j = i+1 ;j <= n ; ++j)
     
    
   

    

     

    
    

     
 if(g[i][j] > dist)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       G[i].push_back(j) ;
     
    
   

    

     

    
    

     

       G[j].push_back(i) ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return  dfs(1 ,0) ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int binary_search(int le ,int rt) //
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 int mid ;
     
    
   

    

     

    
    

     
 while(le < rt)
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       mid = (le + rt)>>1 ;
     
    
   

    

     

    
    

     
 if(judge(d[mid]))  rt = mid ;
     
    
   

    

     

    
    

     
 else  le = mid + 1 ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return le ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     

      int main()
     
    
   

    

     

    
    

     

      {
     
    
   

    

     

    
    

     
 //freopen("input.txt" ,"r" ,stdin) ;
     
    
   

    

     

    
    

     
 while(~scanf("%d%d" ,&n ,&k))
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     

       num = 0 ; d[0] = 0 ;
     
    
   

    

     

    
    

     
 for(int i = 1 ;i <= n ; ++i)
     
    
   

    

     

    
    

     
 scanf("%d%d" ,&P[i].x ,&P[i].y) ;
     
    
   

    

     

    
    

     
 for(int i = 1 ;i < n ; ++i)
     
    
   

    

     

    
    

     
 for(int j = i+1 ;j <= n ; ++j)
     
    
   

    

     

    
    

     

       d[++num] = g[i][j] = (P[i].x-P[j].x)*(P[i].x-P[j].x) + (P[i].y - P[j].y)*(P[i].y-P[j].y) ;
     
    
   

    

     

    
    

     

       sort(d ,d + num + 1) ;
     
    
   

    

     

    
    

     

       num = unique(d ,d+num+1) - d - 1 ;
     
    
   

    

     

    
    

     
 int mx = binary_search(0 ,num) ; // 二分查找最小直径
     
    
   

    

     

    
    

     

       judge(d[mx]) ;
     
    
   

    

     

    
    

     
 bool first = false ;
     
    
   

    

     

    
    

     
 for(int i = n ;i >= 1 ; --i)
     
    
   

    

     

    
    

     
 if(vis[i])
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(first)  putchar(' ') ;
     
    
   

    

     

    
    

     
 printf("%d" ,i) ;
     
    
   

    

     

    
    

     

       k-- ;
     
    
   

    

     

    
    

     

       first = true ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 for(int i = n ;i >= 1 && k > 0 ; --i)
     
    
   

    

     

    
    

     
 if(!vis[i])
     
    
   

    

     

    
    

     

       {
     
    
   

    

     

    
    

     
 if(first)  putchar(' ') ;
     
    
   

    

     

    
    

     
 printf("%d" ,i) ;
     
    
   

    

     

    
    

     

       k-- ;
     
    
   

    

     

    
    

     

       first = true ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 cout<<endl ;
     
    
   

    

     

    
    

     

       }
     
    
   

    

     

    
    

     
 return 0 ;
     
    
   

    

     

    
    

     

      }
     
    
   

    

     

    
    

     
 
     
    
  
 

文章来源: blog.csdn.net，作者：Linux猿，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/nyist_zxp/article/details/40210419