UVa 216 - Getting in Line

언뜻 보기에는 최소 생성 트리처럼 실제 사용하지 않는다. 데이터량이 적기 때문에 전체 배열의 최소값을 직접 모의하면 된다.
코드는 다음과 같습니다.

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;

struct point
{
    int x, y;
} po[10];
int n;
double save_d[10], dis[10], tot, dd;
int max_[10], save_v[10], vis[10];
int solve(int cur, double d)
{
    if(cur == n)
    {
        if(d < tot)
        {
            tot = d;
            for(int i = 0; i < n; i++)
            {
                save_d[i] = dis[i];
                max_[i] = save_v[i];
            }
        }
        return 1;
    }
    for(int i = 0; i < n; i++)
        if(!vis[i])
        {
            if(cur)
            {
                double ans1, ans2;
                ans1 = (double)(po[i].x - po[save_v[cur - 1]].x);
                ans2 = (double)(po[i].y - po[save_v[cur - 1]].y);
                dd = sqrt(ans1 * ans1 + ans2 * ans2);
                dis[cur - 1] = dd;
            }
            else
                dd = 0;
            if(d + dd > tot) //                    ，           
                continue;
            vis[i] = 1;
            save_v[cur] = i;
            solve(cur + 1, d + dd);
            vis[i] = 0;
        }
    return 0;
}
int main()
{
#ifdef test
    freopen("sample.txt", "r", stdin);
#endif
    int num = 1;
    while(scanf("%d", &n), n)
    {
        tot = 1000000;
        memset(vis, 0, sizeof(vis));
        for(int i = 0; i < n; i++)
            scanf("%d%d", &po[i].x, &po[i].y);
        solve(0, 0);
        printf("**********************************************************
");
        printf("Network #%d
", num++);
        for(int i = 0; i < n - 1; i++)
            printf("Cable requirement to connect (%d,%d) to (%d,%d) is %.2lf feet.
", po[max_[i]].x, po[max_[i]].y, po[max_[i + 1]].x, po[max_[i + 1]].y, save_d[i] + 16);
        printf("Number of feet of cable required is %.2lf.
", tot + (n - 1) * 16);
    }
    return 0;
}