UVA 10911 Forming Quiz Teams(dp + 集合最优配对问题)

4th IIUC Inter-University Programming Contest, 2005

G

Forming Quiz Teams

0

#include <stdio.h>#include <string.h>#include <limits.h>#include <math.h>int n, i, j, s;double dp[1<<20];struct Student{char name[105];int x, y;} stu[20];double min(double a, double b) {return a < b ? a : b;}double dis(Student a, Student b) {return sqrt((double)((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y)));}double dpp(int p) {if (dp[p] != -1) return dp[p];dp[p] = INT_MAX;int i, j;for (i = n - 1; i >= 0; i --)if (p & (1 << i))break;for (j = i - 1; j >= 0; j --)if (p & (1 << j))dp[p] = min(dp[p], dis(stu[i], stu[j]) + dpp(p ^ (1<<i) ^ (1<<j)));return dp[p];}int main(){int t = 1;while (~scanf("%d", &n) && n) {n *= 2;s = 1<<n;for (i = 1; i < s; i ++)dp[i] = -1;dp[0] = 0;for (i = 0; i < n; i ++)scanf("%s%d%d", stu[i].name, &stu[i].x, &stu[i].y);printf("Case %d: %.2lf\n", t ++, dpp(s - 1));}return 0;}