首页 > ACM题库 > HDU-杭电 > HDU 4385-Moving Bricks[解题报告]HOJ
2015
05-24

HDU 4385-Moving Bricks[解题报告]HOJ

Moving Bricks

问题描述 :

Brickgao used to be a real tall, wealthy, handsome man and you might know him well. If you don’t, please draw attention to the details below.
Brickgao tried his fortune in investment of golden bricks with his two partners LS and Jne. Because he knew little about investment he gave his total trust and bank savings to his two partners who looked smart.
However, due to the bad luck and lack of business skills, LS and Jne used up Brickgao’s fund, and nothing in return. Their investment failed and the three become diaosi.
Brickgao had no other choice but to earn a living as a construction worker and he found his place on a building site moving bricks which of course was not golden ones. There were many brick fragment scattered on the site and workers had to move them to the building that under construction. Brickgao was made to cope with the task.
The problem is that the Brickgao couldn’t carry more than two bricks at a time since they were too heavy. Also, if he had taken a brick, he couldn’t put it anywhere except the goal building ― his inherent sense of order does not let him do so.
You are given N pairs of coordinates of the bricks and the coordinates of the goal building. It is known that the Brickgao covers the distance between any two points in the time equal to the squared length of the segment between the points. It is also known that initially the coordinates of the Brickgao and the goal building are the same. You are asked to find such an order of bricks, that the Brickgao could move all the bricks to the building in a minimum time period. You can assume the no two bricks shared the same coordinates. If more than one optimum moving sequence Brickgao could find, he would choose the smallest lexicographic one because of the inherent sense of order.

输入:

The first line of the input file contains an integer T which indicates the number of test cases. The first line of each case contains the building’s coordinates x ,y. The second line contains number N (1<= N < 20) ― the amount of bricks on the building site. The following N lines contain the bricks’ coordinates. All the coordinates do not exceed 100 in absolute value. All the given positions are different. All the numbers are integer.

输出:

The first line of the input file contains an integer T which indicates the number of test cases. The first line of each case contains the building’s coordinates x ,y. The second line contains number N (1<= N < 20) ― the amount of bricks on the building site. The following N lines contain the bricks’ coordinates. All the coordinates do not exceed 100 in absolute value. All the given positions are different. All the numbers are integer.

样例输入:

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

样例输出:

Case 1:
8
1 2
Case 2:
32
1 2 3

Hint
In the first test, Brickgao gets brick 1 and brick 2 and returns to the building. In the second test, Brickgao first moves brick 1 and brick 2 to the building and then gets the third and returns to the building.

//#include<cstdio>
//#include<cstring>
//#include<cmath>
//#include<iostream>
//#include<algorithm>
//#include<set>
//#include<map>
//#include<queue>
//#include<vector>
//#include<string>
//
//#define Min(a,b) a<b?a:b
//#define Max(a,b) a>b?a:b
//#define CL(a,num) memset(a,num,sizeof(a));
//#define maxn  30
//#define eps  1e-8
//#define inf 100000000
//#define N  4000000
//#define ll   __int64
//using namespace std;
//
//struct node {
//    int x;
//    int y;
//} a[maxn], ans[maxn];
//
//int cmp(node a, node b) {
//    return a.x < b.x;
//}
//int dp[N], dis[maxn][maxn], pre[N];
//
//int main() {
//    int i, j, n, t, tmp, p, tp, k, x, y;
//    int cas = 0;
//    //freopen("data.txt","r",stdin);
//    scanf("%d", &t);
//    while (t--) {
//        scanf("%d%d", &x, &y);
//        scanf("%d", &n);
//        a[n].x = x;
//        a[n].y = y;
//        for (i = 0; i < n; i++) {
//            scanf("%d%d", &a[i].x, &a[i].y);
//        }
//        for (i = 0; i <= n; i++) {
//            for (j = i + 1; j <= n; j++) {
//                dis[i][j] = dis[j][i] = (a[i].x - a[j].x)*(a[i].x - a[j].x) + (a[i].y - a[j].y)* (a[i].y - a[j].y);
//            }
//        }
//        memset(dp, 0x3f, sizeof (dp));
//        dp[0] = 0;
//        int stat = (1 << n) - 1;
//        for (i = 0; i <= stat; i++) {
//            for (j = 0; j < n; j++) {
//                if (!(i & (1 << j))) {
//                    tp = i | 1 << j;
//                    tmp = dp[i] + 2 * dis[j][n];
//                    if (dp[tp] > tmp) {
//                        dp[tp] = tmp;
//                        pre[tp] = i;
//                    }
//                    for (k = 0; k < n; k++)//濡傛灉涓�娆″幓涓ゅ潡
//                    {
//                        if (!(tp & (1 << k))) {
//                            p = tp | 1 << k;
//                            tmp = dp[i] + dis[j][n] + dis[j][k] + dis[k][n];
//                            if (dp[p] > tmp) {
//                                dp[p] = tmp;
//                                pre[p] = i; // 娉ㄦ剰 杩欓噷鐨勭姸鎬佹槸璁板綍鍘讳袱鍧椾箣鍓嶇殑i
//                            }
//                        }
//                    }
//                }
//            }
//        }
//        printf("Case %d:\n", ++cas);
//        printf("%d\n", dp[stat]);
//        int t = stat;
//        int num = 0;
//        while (t) {
//            bool flag = false;
//            int tmp = t^pre[t];
//            ans[num].y = 25; //鐢ㄦ潵璁板綍涓�娆� 鍙栦袱涓殑绗簩涓厓绱狅紙25琛ㄧず鍒濆鍖栨病鏈夛級
//            for (i = 0; i < n; i++) {
//                if ((tmp >> i)&1) {
//                    if (!flag) {
//                        ans[num].x = i;
//                        flag = true;
//                    } else ans[num].y = i;
//                }
//            }
//            t = pre[t];
//            num++;
//        }
//        sort(ans, ans + num, cmp);
//        for (i = 0; i < num; i++) {
//            if (i == 0)printf("%d", ans[i].x + 1);
//            else printf(" %d", ans[i].x + 1);
//            if (ans[i].y < 25) printf(" %d", ans[i].y + 1);
//        }
//        puts("");
//    }
//}
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>
#include <vector>
using namespace std;
const int MAXN = 22;
const int MAX = 1000010;
int pre[MAX];
int dp[MAX];
int map[MAXN][MAXN];
int num[MAXN];

struct node {
    int x, y;
} Node[MAXN];

int get_dis(node a, node b) {
    return (a.x - b.x)*(a.x - b.x)+(a.y - b.y)*(a.y - b.y);
}
bool cmp(node a, node b) {
    return a.x < b.x;
}
int main() {
    node origion;
    int T;
    int N;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%d%d", &origion.x, &origion.y);
        scanf("%d", &N);
        for (int i = 0; i < N; i++) {
            scanf("%d%d", &Node[i].x, &Node[i].y);
        }
        Node[N] = origion;
        for (int i = 0; i <= N; i++) {
            for (int j = i + 1; j <= N; j++) {
                map[i][j] = map[j][i] = get_dis(Node[i], Node[j]);
            }
        }
        int size = (1 << N);
        memset(dp, -1, sizeof (dp));
        dp[0] = 0;
        int dis;
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < N; j++) {
                if (!(i & (1 << j))) {
                    dis = dp[i] + 2 * map[N][j];
                    if ((dp[i | (1 << j)] == -1) || (dis < dp[i | (1 << j)])) {
                        dp[i | (1 << j)] = dis;
                        pre[i | (1 << j)] = i;
                    }
                    for (int k = j + 1; k < N; k++) {
                        if (!(i & (1 << k))) {
                            dis = dp[i] + map[N][j] + map[j][k] + map[k][N];
                            if ((dp[i | (1 << j) | (1 << k)] == -1) || dis < dp[i | (1 << j) | (1 << k)]) {
                                dp[i | (1 << j) | (1 << k)] = dis;
                                pre[i | (1 << j) | (1 << k)] = i;
                            }
                        }
                    }
                }
            }
        }
//        printf("Case %d:\n", cas);
//        printf("%d\n", dp[size - 1]);
//        int now = size - 1;
//        int stack[MAXN];
//        int top = 0;
//        while (now) {
//            for (int j = N - 1; j >= 0; j--) {
//                if ((1 << j) & (now - pre[now])) {
//                    stack[++top] = j + 1;
//                }
//            }
//            now = pre[now];
//        }
//        printf("%d", stack[top--]);
//        while (top) {
//            printf(" %d", stack[top--]);
//        }
//        printf("\n");
        int n=N;
        vector<node> sta;
        int s = (1 << n) - 1;
        printf("Case %d:\n", cas);
        printf("%d\n", dp[s]);
        while (s) {
            int b = pre[s];
            node ans;
            ans.x = ans.y = -1;
            for (int i = 0; i < n; i++)
                if (((1 << i) & s) && !((1 << i) & b)) {
                    if (ans.x == -1)
                        ans.x = i;
                    else if (ans.y == -1)
                        ans.y = i;
                }
            sta.push_back(ans);
            s = b;
        }
        sort(sta.begin(), sta.end(), cmp);
        int cnt=0;
        for (int i = 0; i < sta.size(); i++) {
            printf("%d%c", sta[i].x + 1, ++cnt == n ? '\n' : ' ');
            if(sta[i].y!=-1)
                 printf("%d%c", sta[i].y + 1, ++cnt == n ? '\n' : ' ');
        }
    }
    return 0;
}