UVA10911 Forming Quiz Teams 题解

#include <iostream>
#include <cmath>
using namespace std;
int n,dis[20004],cnt;//dis是标记数组
double a[2005],b[2005];
string s;
double ans = 1e10;
double ju(int x,int y)//这是两点之间的距离公式
{
	return sqrt((a[x] - a[y]) * (a[x] - a[y]) + (b[x] - b[y]) * (b[x] - b[y]));
}
void dfs(int step,double sum)//step是枚举的点，sum是目前的距离总和
{
	if(sum > ans)return ;
	if(step > 2 * n)
	{
		ans = min(ans,sum);
		return ;
	}
	if(dis[step])dfs(step + 1,sum);
	else
	{
		for(int i = step + 1;i <= 2 * n;i ++)
		{
			if(dis[i])continue ;
			dis[step] = dis[i] = 1;//将这两个点分到一组
			dfs(step + 1,sum + ju(step,i));
			dis[step] = dis[i] = 0;
		}
	}
}
int main()
{
	while(cin >> n && n)
	{
		ans = 1e10;
		for(int i = 1;i <= 2 * n;i ++)cin >> s >> a[i] >> b[i];
		dfs(1,0);
		printf("Case %d: %.2lf\n",++cnt,ans);
	}
}