HDU 1863 畅通工程（prim算法）

转载请注明出处：http://blog.csdn.net/a1dark

分析：这题也是最小生成树的模板题、刚才用了kruskal算法做过了、现在换成prim继续做、其实两种算法的本质一样的、有点贪心的感觉、不过kruskal时以边为基础、prim是以点为基础、所以kruskal适合稀疏图、而prim更适合稠密图、

#include<stdio.h>#define INF 0x3f3f3fint m,n;int map[105][105];int vis[105];int val[105];void init(){    for(int i=1;i<=m;i++)        for(int j=1;j<=m;j++){            if(i==j)                map[i][j]=0;            else                map[i][j]=INF;        }}void prim(){    memset(vis,0,sizeof(vis));    for(int i=1;i<=m;i++)        val[i]=map[1][i];    int sum=0;    vis[1]=1;    for(int i=1;i<m;i++){        int min=INF;        int mink=1;        for(int j=1;j<=m;j++){            if(!vis[j]&&val[j]<min){                min=val[j];                mink=j;            }        }        vis[mink]=1;        sum+=min;        for(int j=1;j<=m;j++){            if(!vis[j]&&map[mink][j]<val[j])                val[j]=map[mink][j];        }    }    if(sum>=INF)        printf("?\n");    else        printf("%d\n",sum);}int main(){    int s,e,v;    while(scanf("%d%d",&n,&m)!=EOF){        if(n==0)break;        init();        for(int i=1;i<=n;i++){            scanf("%d%d%d",&s,&e,&v);            if(v<map[s][e]){                map[s][e]=map[e][s]=v;            }        }        prim();    }    return 0;}