1950.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 1950 on 2006-08-09 at 09:41:38 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int N = 16;
const int INF = 1 << 20;

int g[N][N], s[N], sn, best[1<<N];

int find(int);

int main()
{
	int n, m, d[N];
	int i, j, k;
	
	while(scanf("%d %d", &n, &m) != EOF && n != 0) {
		for(i = 0; i < n; i++)
			for(j = 0; j < n; j++)
				g[i][j] = INF;
		for(i = 0; i < n; i++) g[i][i] = 0;
		int total = 0;
		memset(d, 0, sizeof(d));
		for(i = 0; i < m; i++) {
			int a, b, l; scanf("%d %d %d", &a, &b, &l);
			a--; b--; g[a][b] = g[b][a] <?= l;
			total += l;
			d[a]++; d[b]++;
		}
		for(k = 0; k < n; k++)
			for(i = 0; i < n; i++)
				for(j = 0; j < n; j++)
					g[i][j] <?= g[i][k]+g[k][j];
		for(sn = i = 0; i < n; i++)
			if(d[i]&1) s[sn++] = i;
		memset(best, -1, sizeof(best));
		best[0] = 0;
		printf("%d\n", find((1<<sn)-1)+total);
	}
	
	return 0;
}

int find(int st)
{
	int i, j;
	if(best[st] == -1) {
		best[st] = INF;
		for(i = 0; i < sn; i++)
			for(j = i+1; j < sn; j++)
				if((st&(1<<i)) && (st&(1<<j))) 
					best[st] <?= find(st^(1<<i)^(1<<j))+g[s[i]][s[j]];
	}
	return best[st];
}