本文主要是介绍hdu 1863畅通工程(prim,邻接矩阵)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：acm.hdu.edu.cn/showproblem.php?pid=1863
最小生成树的简单应用。直接用邻接矩阵即可，用链式前向星好像有点问题。由于输入边的顺序，村子的顺序是未知的，所以只能最开始：
tag[edge[1].to]=1;
for(i=head[edge[1].to];i>0;i=edge[i].next)dis[i]=edge[i].w;
或者：tag[1]=1;
for(i=head[1];i>0;i=edge[i].next)dis[i]=edge[i].w;
但这样一来就有可能出现遍历中断的问题。在无向图中，同样的边仅仅输入一次，如果输入3 1 4；用上述代码查找不能通过1找到3.
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,i,j; //n,m: path and country
const int INF=0x3f3f3f3f,maxn=150;
int map[maxn][maxn];
void show(){cout<<"-------------"<<endl;for(i=1;i<=m;i++){for(j=1;j<=m;j++){printf("%d %d %d\n",i,j,map[i][j]);}}
}
void inimap(){for(i=1;i<=m;i++){for(j=1;j<=m;j++){if(i==j)map[i][j]=0;else map[i][j]=INF;}}
}
int prim(){int ans=0,dis[maxn];bool tag[maxn];memset(tag,0,sizeof(tag));tag[1]=1;for(i=1;i<=m;i++)dis[i]=map[1][i];int mmin,k;for(i=1;i<m;i++){mmin=INF;k=0;for(j=1;j<=m;j++){if(!tag[j]&&mmin>dis[j]){mmin=dis[j];k=j;}}if(k==0)return 0;tag[k]=1;ans+=dis[k];//cout<<"ans:"<<ans<<endl;for(j=1;j<=m;j++){if(!tag[j]&&dis[j]>map[k][j]&&map[k][j]!=INF)dis[j]=map[k][j];}}return ans;
}
int main()
{//freopen("cin.txt","r",stdin);while(cin>>n&&n){scanf("%d",&m);inimap(); //当i==j时应取0，当两点不相接时取无穷，这里统一用-1for(i=0;i<n;i++){int a,b,c;scanf("%d%d%d",&a,&b,&c);map[a][b]=c;map[b][a]=c;}//show();int ans=prim();if(!ans)printf("?\n");else printf("%d\n",ans);}return 0;
}
这篇关于hdu 1863畅通工程(prim,邻接矩阵)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
