首页 > ACM题库 > HDU-杭电 > hdu 2295 Radar -DFS-[解题报告]C++
2014
01-05

hdu 2295 Radar -DFS-[解题报告]C++

Radar

问题描述 :

N cities of the Java Kingdom need to be covered by radars for being in a state of war. Since the kingdom has M radar stations but only K operators, we can at most operate K radars. All radars have the same circular coverage with a radius of R. Our goal is to minimize R while covering the entire city with no more than K radars.

输入:

The input consists of several test cases. The first line of the input consists of an integer T, indicating the number of test cases. The first line of each test case consists of 3 integers: N, M, K, representing the number of cities, the number of radar stations and the number of operators. Each of the following N lines consists of the coordinate of a city.
Each of the last M lines consists of the coordinate of a radar station.

All coordinates are separated by one space.
Technical Specification

1. 1 ≤ T ≤ 20
2. 1 ≤ N, M ≤ 50
3. 1 ≤ K ≤ M
4. 0 ≤ X, Y ≤ 1000

输出:

The input consists of several test cases. The first line of the input consists of an integer T, indicating the number of test cases. The first line of each test case consists of 3 integers: N, M, K, representing the number of cities, the number of radar stations and the number of operators. Each of the following N lines consists of the coordinate of a city.
Each of the last M lines consists of the coordinate of a radar station.

All coordinates are separated by one space.
Technical Specification

1. 1 ≤ T ≤ 20
2. 1 ≤ N, M ≤ 50
3. 1 ≤ K ≤ M
4. 0 ≤ X, Y ≤ 1000

样例输入:

1
3 3 2
3 4
3 1
5 4
1 1
2 2
3 3

样例输出:

2.236068

Radar

题意:有N个城市,M个雷达站,K个操作员,从M个雷达站中选择K个,来覆盖所有的N城市,每个雷达有相同的覆盖半径,问:最小的覆盖半径是多少

一看题意,就知道是个最小支配集问题,最小支配集属于NP难题,找不到多项式解法,所有只能搜索,但是普通的搜索是过不了的,鉴于这种类型的题,可以用一种的特殊的结构–双向链表,于是就可以用DLX来优化这个搜索,而且这题还需要剪枝,据说是A*,表示不懂,找到模板过了。。

可以先二分距离,然后用DLX判断就行了。

 

/*最小支配集*/
 #include<stdio.h>
 #include<string.h>
 #include<math.h>
 #include<stdlib.h>
  #define INF 0x3fffffff
  #define EPS 1e-8
  #define EP 1e-10
  #define NN 55
 struct POINT{
        double x, y;
 }f[NN], g[NN];
 double dis[NN][NN];
 
 int adj[NN][NN];
 int N, M, K, head;
 
 int R[NN * NN], L[NN * NN], U[NN * NN], D[NN * NN];
 int C[NN * NN];//记录每个节点所在列 
 int cntc[NN]; //记录每列包含的节点数 
 
 /*删除第c列*/ 
 void remove(int c){
     int i;
     for (i = D[c]; i != c; i = D[i]){
         R[L[i]] = R[i];
         L[R[i]] = L[i];        
     }
 }
 /*恢复第c列*/ 
 void resume(int c){
     int i;
     for (i = D[c]; i != c; i = D[i]){
         R[L[i]] = i;
         L[R[i]] = i;        
     }
 }
 
 int h(){
     bool hash[NN];
     memset(hash, 0, sizeof(hash));
     
     int i, j, c;
     int ans = 0;
     for (c = R[head]; c != head; c = R[c]){
         if (!hash[c]){
            ans ++;
            for (i = D[c]; i != c; i = D[i]){
                for (j = R[i]; j != i; j = R[j]){
                    hash[C[j]] = true;
                }
            }
         }
     }
     return ans;    
 }
 
 /*DLX主要部分*/ 
 int dfs(int k){
     if (R[head] == head) return 1;
     if (k + h() > K) return 0;// A*剪枝 
     
     
     int i, j, c;
     int Min = INF;
     for (i = R[head]; i != head; i = R[i]){
         if (cntc[i] < Min){
            Min = cntc[i];
            c = i;
         }
     }
     for (i = D[c]; i != c; i = D[i]){
         remove(i);
         for (j = R[i]; j != i; j = R[j]){
             remove(j);
             cntc[C[j]]--;
         }
         if (dfs(k + 1)) return 1;
         for (j = L[i]; j != i; j = L[j]){
             resume(j);
             cntc[j]++;
         }
         resume(i);
     }
     return 0;
 }
 /*建图*/ 
 int Build(){
      int i, j, now, pre, first;
      head = 0;
      for (j = head; j < N; j++){
          R[j] = j + 1;
          L[j + 1] = j;    
      }
      L[head] = j;
      R[j] = head;
      
      /*列双向链表*/
      for (j = 1; j <= N; j++){
          pre = j;
          cntc[j] = 0;
          for (i = 1; i <= M; i++){
              if (adj[i][j]){
                 now = i * N + j;
                 C[now] = j;
                 cntc[j]++;
                 D[pre] = now;
                 U[now] = pre;
                 pre = now;
              }
          }
          now = j;
          D[pre] = now;
          U[now] = pre;
          if (cntc[j] == 0) return 0;
      }
      /*行双向链表*/
      for (i = 1; i <= M; i++){
          pre = first = -1;
          for (j = 1; j <= N; j++){
              if (adj[i][j]){
                 now = i * N + j;
                 if (pre != -1){
                         R[pre] = now;
                         L[now] = pre;
                 }else{
                       first = now;
                 }
                 pre = now;
              }
          }
          if (first != -1){
             now = first;
             R[pre] = now;
             L[now] = pre;
          }
      }
      return 1;
 }
 
 /*判断*/ 
 int OK(double mid){
     int i, j;
     for (i = 1; i <= M; i++){
         for (j = 1; j <= N; j++){
             if (dis[i][j] - mid < EP){
                adj[i][j] = 1;
             }else adj[i][j] = 0;
         }
     }
     if (Build())
     return dfs(0);
     else return 0;
 }
 
 /*二分距离*/
 double Binary(){
        double low = 0;
        double hig = 1500;
        double mid, ans = -1;
        while(hig - low > EPS){
            mid = (low + hig) / 2;
            if (OK(mid)){
               ans = mid;
               hig = mid;
            }else low = mid;
        }
        return ans;
 }
 /*计算雷达i到城市j的距离*/
 double Distance(int i, int j){
        return sqrt((g[i].x - f[j].x) * (g[i].x - f[j].x) 
        + (g[i].y - f[j].y) * (g[i].y - f[j].y));
 }
 /*初始化距离矩阵dis[M][N]*/ 
 void Init(){
      int i, j;
      for (i = 1; i <= M; i++){
          for (j = 1; j <= N; j++){
              dis[i][j] = Distance(i, j);
          }
      }
 }
 int main()
 {
     int T, i;
     scanf("%d", &T);
     while(T--){
        scanf("%d%d%d", &N, &M, &K);
        for (i = 1; i <= N; i++){
            scanf("%lf%lf", &f[i].x, &f[i].y);
        }
        for (i = 1; i <= M; i++){
            scanf("%lf%lf", &g[i].x, &g[i].y);
        }
        Init();
        printf("%.6lf\n", Binary());
     }
     return 0;
 }

 

 

 

解题转自:http://www.cnblogs.com/ylfdrib/archive/2010/10/03/1841724.html


  1. 为什么for循环找到的i一定是素数叻,而且约数定理说的是n=p1^a1*p2^a2*p3^a3*…*pk^ak,而你每次取余都用的是原来的m,也就是n