UVA10911 Forming Quiz Teams 题解

· · 题解

题目传送门

注意到 n \le 8，这种范围并不需要状压 dp，普通的 dfs 也可以过。

从 1 号点开始枚举，如果一个点已经打了标记，说明这个点已经和其他点配对，直接枚举下一个点；否则再枚举一个点，并将枚举的两个点配对并打上标记。

注意需要回溯！！！

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