UVA 216 Getting in Line

 

大意：给你一些定点，让你以代价最小的边将所有的点连起来。

 

思路：数据范围很小，可以通过最小生成树或者回溯来解决。

 

最小生成树去写时不知道哪错了，于是用回溯模拟了一遍，相当于模拟一个数组的全排列。

 

AC CODE：

 

#include 

#include 

#include 

#include 

#include      //INT_MAX,整形范围内的最大整数。

#include 

using namespace std;



#define INF 0x3f3f3f3f

const int SIZE = 110;



double d[SIZE];

int vis[SIZE], save[SIZE], ans[SIZE];

int n;

double Min;



struct node

{

    double x, y;

}a[SIZE];



double fun(const node a, const node b)

{

    return sqrt((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y));

}



void init()

{

    memset(vis, 0, sizeof(vis));

    for(int i = 0; i < n; i++) ans[i] = i;

    Min = INF;

}



void dfs(int cur, double sum)

{

    if(cur == n)

    {

        if(Min > sum)

        {

            Min = sum;

            memcpy(ans, save, sizeof(save));

        }

        return ;

    }

    if(sum >= Min) return ;

    for(int i = 0; i < n; i++) if(!vis[i])

    {

        vis[i] = 1;

        save[cur] = i;

        if(cur == 0)

        {

            dfs(cur+1, 0);

        }

        else

        {

            double dis = fun(a[save[cur]], a[save[cur-1]]);

            dfs(cur+1, sum+dis);

        }

        vis[i] = 0;

    }

}



int main()

{

    int times = 0;

    while(~scanf("%d", &n) && n)

    {

        init();

        for(int i = 0; i < n; i++)

        {

            scanf("%lf%lf", &a[i].x, &a[i].y);

        }

        dfs(0, 0);

        printf("**********************************************************
");

        printf("Network #%d
", ++times);

        for(int i = 1; i < n; i++)

        {

            double dis = fun(a[ans[i]], a[ans[i-1]]) + 16.00;

            printf("Cable requirement to connect (%.lf,%.lf) to (%.lf,%.lf) is %.2lf feet.
", a[ans[i-1]].x, a[ans[i-1]].y, a[ans[i]].x, a[ans[i]].y, dis);

        }

        double tot = (n-1)*16.00;

        printf("Number of feet of cable required is %.2lf.
", Min+tot);

    }

}

 

WA CODE：

 

#include 

#include 

#include 

#include 

#include      //INT_MAX,整形范围内的最大整数。

#include 

using namespace std;



#define INF 0x3f3f3f3f

const int SIZE = 110;





double w[SIZE][SIZE];

double d[SIZE];

int v[SIZE];

int n;



struct node

{

    double x, y;

}a[SIZE];



double fun(const node a, const node b)

{

    return sqrt((b.x - a.x) * (b.x - a.x) + (b.y - a.y) * (b.y - a.y));

}



double Prim(int src)

{

    int i, j, first = 0;

    double cnt = 0;

    int pre = src;

    for(i = 1; i <= n; i++) d[i] = (i == src)? 0:INF;

    for(i = 1; i <= n; i++)

    {

        int x;

        double m = INF;

        for(int y = 1; y <= n; y++) if(!v[y] && m > d[y]) m = d[x=y];

        v[x] = 1;

        cnt += m;

        if(first)

        {

            printf("Cable requirement to connect (%.lf,%.lf) to (%.lf,%.lf) is %.2lf feet.
", a[pre].x, a[pre].y, a[x].x, a[x].y, m+16);

        }

        for(int y = 1; y <= n; y++) d[y] = min(d[y], w[x][y]);

        pre = x;

        first = 1;

    }

    return cnt;

}



void init()

{

    memset(v, 0, sizeof(v));

    memset(d, 0, sizeof(d));

    memset(a, 0, sizeof(a));

    for(int i = 1; i <= SIZE; i++)

        for(int j = 1; j <= SIZE; j++)

            w[i][j] = w[j][i] = INF;

}







int main()

{

    int i, j;

    int times = 0;

    while(~scanf("%d", &n) && n)

    {

        init();

        for(i = 1; i <= n; i++)

        {

            scanf("%lf%lf", &a[i].x, &a[i].y);

        }

        for(i = 1; i <= n; i++)

        {

            for(j = 1; j <= n; j++)

            {

                if(i == j) continue;

                w[i][j] = w[j][i] = fun(a[i], a[j]);

            }

        }

        printf("**********************************************************
");

        printf("Network #%d
", ++times);

        double ans = Prim(1);

        double tot = (n-1)*16.00;

        printf("Number of feet of cable required is %.2lf.
", ans+tot);

    }

    return 0;

}