首页 > ACM题库 > HDU-杭电 > HDU 3362-Fix-动态规划-[解题报告]HOJ
2014
03-16

HDU 3362-Fix-动态规划-[解题报告]HOJ

Fix

问题描述 :

There are a few points on a plane, and some are fixed on the plane, some are not. We want to connect these points by some sticks so that all the points are fixed on the plane. Of course, we want to know the minimum length of the sum of the sticks.
ASCII
As in the images, the black points are fixed on the plane and red ones are not, which need to be fixed by sticks.
All the points in the left image have been fixed. But the middle one is not, which we need add one stick to fix those four points (the right image shows that stick). Triangle is steady, isn’t it?

输入:

The input consists of multiply test cases. The first line of each test case contains one integer, n (1 <= n <= 18), which is the number of points. The next n lines, each line consists of three integers, x, y, c (0 <= x, y < 100). (x, y) indicate the coordinate of one point; c = 1 indicates this point is fixed; c = 0 indicates this point is not fixed. You can assume that no two points have the same coordinate.
The last test case is followed by a line containing one zero, which means the end of the input.

输出:

The input consists of multiply test cases. The first line of each test case contains one integer, n (1 <= n <= 18), which is the number of points. The next n lines, each line consists of three integers, x, y, c (0 <= x, y < 100). (x, y) indicate the coordinate of one point; c = 1 indicates this point is fixed; c = 0 indicates this point is not fixed. You can assume that no two points have the same coordinate.
The last test case is followed by a line containing one zero, which means the end of the input.

样例输入:

4
0 0 1
1 0 1
0 1 0
1 1 0
3
0 0 1
1 1 0
2 2 0
0

样例输出:

4.414214
No Solution

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

 

题意:题目给出n(n <= 18)个点的二维坐标,并说明某些点是被固定了的,其余则没固定,要求添加一些边,使得还没被固定的点变成固定的,可见题目中的图形sample。
 
由于n很小,而且固定点的顺序没有限制,所以需要用状态压缩DP。这里要注意两点:
 
·当一个没固定的点和两个固定了的点连接后,该点就被间接固定了(三角形的稳定性质)
·无论是直接固定还是间接固定的点,都可以供以后的点用于固定。
 
因此,对于当前需要固定的点,在已经是固定状态的点中选出两个距离当前点最小的,这就保证了局部最优,从起始状态开始转移,最后判断能否到达最终目标状态就可以了。
 
代码:
// 3218 MS
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define inf 1e9
using namespace std;
 
pair<int, int> point[20];
bool fix[20];
double dp[1<<18];
 
double Distance(int a, int b) {
// 计算两点距离
    int x1 = point[a].first, y1 = point[a].second;
    int x2 = point[b].first, y2 = point[b].second;
    return sqrt(1.0*(x1 - x2)*(x1 - x2) + (y1 - y2)*(y1 - y2));
}
 
double Fixed(int n, int state, int cur) {
// 计算当前状态state下,使cur这个点变成fixed所花费的最小代价
    double ans = 0;
    bool mark[20];
    double dist[20];
    for (int i = 0; i < n; ++i) {
    // 检查哪些点是已经fixed的点
        if (((1<<i) & state)) {
            mark[i] = 1;
            dist[i] = Distance(i, cur);
        }
        else
            mark[i] = 0;
    }
    for (int i = 0; i < 2; ++i) {
    // 从已经fixed的点中选择两个最接近当前点的进行连接
        double Min = inf;
        int p = 19;
        for (int j = 0; j < n; ++j) {
            if (mark[j] && dist[j] < Min) {
                Min = dist[j];
                p = j;
            }
        }
        ans += Min;
        mark[p] = 0;
    }
    if (ans >= inf) return -1;
    return ans;
}
 
int main() {
    int n;
    while (cin>>n) {
        if (!n) break;
        int begin = 0, target = 0;
        for (int i = 0; i < n; ++i) {
            cin>>point[i].first>>point[i].second>>fix[i];
            if (fix[i])
                begin += (1<<i);
            target += (1<<i);
            // 顺便计算起始状态、目标状态
        }
        for (int i = 0; i < (1<<n); ++i)
            dp[i] = inf;
        dp[begin] = 0;
 
        for (int i = begin; i < target; ++i) {
        // 状态的遍历
            if (dp[i] == inf) continue;
            for (int j = 0; j < n; ++j) {
            // 每次选择一个还没fixed的点
                if (i & (1<<j)) continue;
                double sum = Fixed(n, i, j);
                if (sum >= 0)
                    dp[i|(1<<j)] = min(dp[i|(1<<j)], dp[i] + sum);
            }
        }
        if (dp[target] == inf)
            printf("No Solution\n");
        else
            printf("%.6lf\n", dp[target]);
    }
    return 0;
}

参考:http://blog.csdn.net/night__elf/article/details/8439293


  1. Gucci New Fall Arrivals

    This is really nice to know. I hope it will be successful in the future. Good job on this and keep up the good work.