2011-06-15 07:44:15Morris
d879. Q10911: Forming Quiz teams
http://zerojudge.tw/ShowProblem?problemid=d879
內容 ：
你被指派一個任務要組隊參加一個猜謎比賽 （MCA CPCI Quiz Championship）。有 2*N 個學生有興趣參加，而你要把他們組成 N 隊，每隊2個人。由於隊友間需要在一起練習，學生們都希望隊友的家盡可能離自己的家近一些。令 x1 代表第1隊隊員家之間的距離，x2 代表第2隊隊員家之間的距離，依此類推。你必須要確保 x1+x2+x3+...+xn 為最小。
輸入說明
：
輸入含有多組測試資料。每組測試 資料的第一列，有 1 個正整數 N （ N <= 8）。接下來的 2*N 列為學生的資訊。每列開始有學生的姓名，然後有學生家的座標（x,y），x,y均為介於 0 到 1000 之間的整數。學生的名字僅包含小寫英文字母，且長度最長 20。
當 N=0 時代表輸入結束，請參考Sample Input。
輸出說明
：
對每一組測試資料輸出一列，輸出如題目所述的距離，就是x1+x2+x3+...+xn 最小為多少。請四捨五入到小數點後2位。輸出格式請參考Sample Output。
範例輸入 ：
5 sohel 10 10 mahmud 20 10 sanny 5 5 prince 1 1 per 120 3 mf 6 6 kugel 50 60 joey 3 24 limon 6 9 manzoor 0 0 1 derek 9 9 jimmy 10 10 0
範例輸出 ：
Case 1: 118.40 Case 2: 1.41
提示
：
匹配一定可以過
何不試試DP呢?
出處
：
UVa ACM 10911
(管理：david942j)
作法 : 資料數據化 & DP & 剪枝 & 暴力
其實看過網路上的作法，並不是很了解，感覺我的作法不太像是DP，有一部份是用剪的
原本想用A* 直接去暴力的 XD，H(x)懶得估算
作法，我晚點在詳細說明，我先去學校了，若我忘記的話，記得提醒我
作法 : 資料數據化 & DP & 剪枝 & 暴力
其實看過網路上的作法，並不是很了解，感覺我的作法不太像是DP，有一部份是用剪的
原本想用A* 直接去暴力的 XD，H(x)懶得估算
作法，我晚點在詳細說明，我先去學校了，若我忘記的話，記得提醒我
/**********************************************************************************/
/* Problem: d879 "Q10911: Forming Quiz teams" from UVa ACM 10911 */
/* Language: C */
/* Result: AC (272ms, 1168KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-15 07:25:17 */
/**********************************************************************************/
#include<stdio.h>
#include<math.h>
struct coordinate {
short x, y;
}D[16];
unsigned short lowbit[65537], next[65537];
char lowbits[65537], set[65537];
double Map[16][16], best[65537];
double DP(int N, int sum) {
if(N == 0) return 0;
if(best[N] != -1) {
return best[N];
}
if(best[sum] == -1)
best[sum] = DP(sum, 0);
int e = lowbits[N], tn, t;
double min = 2000, temp;
sum += lowbit[N], tn = next[N], t = next[N];
for(; t; t = next[t]) {
temp = DP(tn-lowbit[t], sum+lowbit[t]);
min = (min < Map[e][lowbits[t]] + temp) ? min : Map[e][lowbits[t]] + temp;
}
best[N] = min;
return best[N];
}
int Input() {
char cha;
unsigned int x = 0;
while(cha = getchar())
if(cha != ' ' && cha != '\n' || cha == EOF) break;
if(cha == EOF) return -1;
x = cha-48;
while(cha = getchar()) {
if(cha == ' ' || cha == '\n') break;
x = x*10 + cha-48;
}
return x;
}
main() {
int N, a, b, s2[20] = {1}, C = 0;
for(a = 1; a < 17; a++) s2[a] = s2[a-1]*2, set[s2[a]] = a;
for(a = 1; a <= 65536; a++)
lowbit[a] = a & (-a), next[a] = a - lowbit[a], lowbits[a] = set[lowbit[a]];
char name[30];
while(scanf("%d", &N) == 1 && N) {
N *= 2;
for(a = 0; a < N; a++) {
scanf("%s", name);
D[a].x = Input(), D[a].y = Input();
}
for(a = 0; a < N; a++)
for(b = a+1; b < N; b++)
Map[a][b] = sqrt((D[a].x-D[b].x)*(D[a].x-D[b].x) + (D[a].y-D[b].y)*(D[a].y-D[b].y))
, Map[b][a] = Map[a][b];
for(a = 0; a < s2[N]; a++) best[a] = -1;
printf("Case %d: %.2lf\n", ++C, DP(s2[N]-1, 0));
}
return 0;
}