POJ - 1287 Networking（最小生成树，Prim算法）

POJ - 1287

模板题，直接用邻接矩阵存起来，然后用Prim算法，算出最小生成树的长度，注意可能有重边

#include<cstdio>
#include<cstring>
const int INF = 1e9;
int e[101][101],dis[101],vis[101];
int n;
void Prim()
{
    memset(vis,0,sizeof(vis));for(int i=1;i<=n;i++) dis[i]=e[1][i];vis[1]=1;dis[1]=0;int ans=0;for(int i=1;i<=n-1;i++) {
    int minn=INF,u;for(int j=1;j<=n;j++) {
    if(!vis[j]&&minn>dis[j]) {
    minn=dis[j];u=j;}} vis[u]=1;ans+=minn;for(int j=1;j<=n;j++) {
    if(!vis[j]&&dis[j]>e[u][j])dis[j]=e[u][j];}}printf("%d\n",ans);
} 
int main()
{
    int m,a,b,c;while(scanf("%d",&n)&&n) {
    memset(e,0x3f,sizeof(e));scanf("%d",&m);while(m--){
    scanf("%d%d%d",&a,&b,&c);if(e[a][b]>=c) e[a][b]=e[b][a]=c;}Prim();        }return 0;
}