Poj 3771 hdu 3405

wiki Prim http://zh.wikipedia.org/wiki/%E6%99%AE%E6%9E%97%E5%A7%86%E7%AE%97%E6%B3%95

prim 算法水题

之前写过类似的题，一直以为直接暴力，从遍历所有的点为起点，寻找距离起点最短的点然后再在改点上寻找最短距离这摆明了是划线嘛……根本不是图论啊啊啊！！！！

这样真是萌萌哒……

正确的做法是先枚举所有的点作为起点，然后把距离长的点更新

这是主要的思路代码

int lowcost[MAXN]; 
int prim(int v0){
    for(int i = 0;i < n;i++){ //初始化
        lowcost[i] = cost[v0][i];
    }
    int ans = 0;
    for(int i = 0;i < n-1;i++){
        int mindis = INF;
        int minone; //用来标记最小距离
        for(j = 0;j < n;j++){
            if(lowcost[j] && mindis > lowcost[j]){
                mindis = lowcost[j];
                minone = j;
            }
            ans += lowcost[minone];
            lowcost[minone] = 0;
            for(int j = 0;j < n;j++){ //进行更新
                if(cost[minone][j] < lowcost[j]){
                    lowcost[j] = cost[j][minone];
                }
            }
        }
    }
    return ans;
}

代码：非原创……！！！！

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <cstdlib>

const int MAXN = 50 + 10;
const double ESP = 10e-8;
const double Pi = atan(1.0) * 4;
const int INF = 0xffffff;
const int MOD = 10000007;

using namespace std;
struct Point{
    int x;
    int y;
};
Point a[MAXN];
bool vis[MAXN];
int n;
double graph[MAXN][MAXN];
double getl(int i,int j){
    int x = a[i].x - a[j].x;
    int y = a[i].y - a[j].y;
    return sqrt(1.0*x*x+1.0*y*y);
}
double prim(int x){
    int mark;
    bool vis[MAXN];
    memset(vis,0,sizeof(vis));
    vis[x] = 1;
    double dis[MAXN];
    for(int i = 0;i < n;i++){
        dis[i] = graph[i][0];
    }
    vis[0] = 1;
    if(!x){
        for(int i = 0;i < n;i++){
            dis[i] = graph[i][1];
        }
        vis[1] = 1;
    }
    double MIN,SUM = 0;
    for(int k = 1;k < n-1;k++){
        MIN = INF;
        for(int i = 0;i < n;i++){
            if(!vis[i] && MIN > dis[i]){
                MIN = dis[i];
                mark = i;
            }
        }
        SUM += MIN;
        vis[mark] = 1;
        for(int i = 0;i < n;i++){
            if(!vis[i] && dis[i] > graph[mark][i]){
                dis[i] = graph[mark][i];
            }
        }
    }
    return SUM;
}
int main(){
   // freopen("input.txt","r",stdin);
    int t;
    scanf("%d",&t);
    while(t--){
        scanf("%d",&n);
        for(int i = 0;i < n;i++){
            scanf("%d%d",&a[i].x,&a[i].y);
        }
        for(int i = 0;i < n;i++){
            for(int j = 0;j <= i;j++){
                graph[i][j] = graph[j][i] = getl(i,j);
            }
        }
        double h,g = INF;
        for(int i = 0;i < n;i++){
            h  = prim(i);
            g = min(g,h);
        }
        printf("%.2lf
",g);
    }
    return 0;
}

View Code