﻿ UVA 10911 Forming Quiz Teams(dp + 集合最優配對問題)_電腦知識網

# UVA 10911 Forming Quiz Teams(dp + 集合最優配對問題)

2022-06-13   來源: Web編程 You have been given the job of forming the quiz teams for the next MCA CPCI Quiz Championship There are*N students interested to participate and you have to form N teams each team consisting of two members Since the members have to practice together all the students want their members house as near as possible Let x be the distance between the houses of group x be the distance between the houses of group and so on You have to make sure the summation (x + x + x + … + xn) is minimized

Input

There will be many cases in the input file Each case starts with an integer N (N ≤ ) The next *Nlines will given the information of the students Each line starts with the students name followed by thex coordinate and then the y coordinate Both x y are integers in the range to Students name will consist of lowercase letters only and the length will be at most

Input is terminated by a case where N is equal to

Output

For each case output the case number followed by the summation of the distances rounded to decimal places Follow the sample for exact format 題意給定n*n個人分成兩人一組的n組每個人在一個坐標上要求出所有組的兩人距離的和最小

思路明顯的集合最優配對問題i最為前i個人s作為前i個人能組成的所有集合j為前i個人中的一個人

這樣狀態轉移方程為dp[i][s] =min(dp[i][s] dis(i j) + dp[i ][s {i} {j}]集合用二進制來表示所以方程變為

dp[i][s] =min(dp[i][s] dis(i j) + dp[i ][s ^ <<i ^ <<j]但是這樣做時間不是很理想然後看了個詳細解法

裡面講得挺詳細的可以轉化為

代碼

#include <stdioh> #include <stringh> #include <limitsh> #include <mathh> int n i j s; double dp[<<]; struct Student{ char name[]; int x y; } stu[]; double min(double a double b) { return a < b ? a : b; } double dis(Student a Student b) { return sqrt((double)((ax bx) * (ax bx) + (ay by) * (ay by))); } double dpp(int p) { if (dp[p] != ) return dp[p]; dp[p] = INT_MAX; int i j; for (i = n ; i >= ; i ) if (p & ( << i)) break; for (j = i ; j >= ; j ) if (p & ( << j)) dp[p] = min(dp[p] dis(stu[i] stu[j]) + dpp(p ^ (<<i) ^ (<<j))); return dp[p]; } int main(){ int t = ; while (~scanf(%d &n) && n) { n *= ; s = <<n; for (i = ; i < s; i ++) dp[i] = ; dp[] = ; for (i = ; i < n; i ++) scanf(%s%d%d stu[i]name &stu[i]x &stu[i]y); printf(Case %d: %lfn t ++ dpp(s )); } return ; }

From:http://tw.wingwit.com/Article/program/Web/201404/30639.html