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; }