hdu 1162 Eddy's picture（基礎最小生成樹）

題目：

連接：點擊打開鏈接

題意：

n個點，是每個點相互連通（直接間接），求最短距離。

思路：

prim（）最小生成樹。把點的距離存在map中。

代碼：

#include
#include
#include
#include
using namespace std;
#define MAXN 110
#define MAX 100000000

struct node{
    double x,y;
}p[MAXN];

double map[MAXN][MAXN];
double low[MAXN];
int vis[MAXN];
int n;

void prim()
{
    int pos;
    double minn;
    double result = 0;
    memset(vis,0,sizeof(vis));
    pos = 1;
    vis[pos] = 1;
    for(int i=1; i<=n; i++)
    {
        if(i != pos)
            low[i] = map[pos][i];
    }
    for(int i=1; i low[j])
            {
                minn = low[j];
                pos = j;
            }
        }
        result += minn;
        vis[pos] = 1;
        for(int j=1; j<=n; j++)
        {
            if(!vis[j] && map[pos][j] < low[j])
                low[j] = map[pos][j];
        }
    }
    printf("%.2lf\n",result);
}

int main()
{
    //freopen("input.txt","r",stdin);
    while(scanf("%d",&n) != EOF)
    {
        for(int i=1; i<=n; i++)
            scanf("%lf%lf",&p[i].x,&p[i].y);
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
                map[i][j] = sqrt((p[i].x-p[j].x)*(p[i].x-p[j].x) + (p[i].y-p[j].y)*(p[i].y-p[j].y));
        }
        prim();
    }
    return 0;
}

戰斗，永不停歇~~~~~~~~~~~~~~~~~~~~~