UVa-10911 : Forming Quiz Teams

問題概要

ノード数N(<16, even)の重み付き完全グラフが与えられるので最小重みマッチングを求める問題。

解法

ICPCの国内予選に出たAnd Then. How Many Are There?に似てる。ビットDPするだけ。

acceptされたコード

計算量O(2^N * N^2)。

#include <cstdio>
#include <cmath>
#include <algorithm>
using namespace std;

const int MAX_N = 8;
const double INF = 1e9;
const double EPS = 1e-9;

int N;
double dp[1<<(MAX_N*2)];
double graph[MAX_N * 2][MAX_N * 2];

int xs[MAX_N * 2], ys[MAX_N * 2];

double sq(double x){
	return x * x;
}

double dist(int x1, int y1, int x2, int y2){
	return sqrt(sq(x1 - x2) + sq(y1 - y2));
}

bool init(){
	scanf("%d ", &N);
	N *= 2;
	for(int i=0; i<N; i++){
		scanf("%*s %d %d ", xs + i, ys + i);
	}

	return N > 0;
}

double solve(){
	for(int i=0; i<N; i++){
		for(int j=0; j<N; j++){
			graph[i][j] = dist(xs[i], ys[i], xs[j], ys[j]);
		}
	}

	fill(dp, dp + (1<<N), INF);
	dp[0] = 0;

	for(int bit=0; bit<(1<<N); bit++)if(!__builtin_parity(bit)){
		for(int i=0; i<N; i++)if( !((bit>>i)&1) ){
			for(int j=i+1; j<N; j++)if( !((bit>>j)&1) ){
				int nbit = bit | (1<<i) | (1<<j);
				dp[nbit] = min(dp[nbit], dp[bit] + graph[i][j]);
			}
		}
	}

	return dp[(1<<N)-1];
}

int main(){
	int c = 0;
	while(init()){
		printf("Case %d: %.2f\n", ++c, solve() + EPS);
	}

	return 0;
}