首页 > 学院 > 开发设计 > 正文

(最小生成树)HDU 1863 畅通工程

2019-11-06 09:06:40
字体:
来源:转载
供稿:网友

查看原题

题意

最小生成树

思路

PRim算法

代码

#include <iostream>using namespace std;int main(int argc, char *argv[]){ int m,n,num[105][105],a,b,x; while(cin>>n>>m&&n){ int visted[105]={0}; for(int i=1;i<=m;i++){//数组先过一遍 for(int j=1;j<=m;j++){ num[i][j]=999999; } } for(int i=0;i<n;i++){//输入值 cin>>a>>b>>x; if(x<num[a][b]){ num[a][b]=x; } } int low[105]={999999},step=1,temp,sum=0,i,j; for(int i=1;i<=m;i++){//设立一个一维数组,一步步存储更新距离 low[i]=num[step][i]; } visted[step]=1;//把1并入 for(i=1;i<m;i++){//因为1已经走过,再找只需要再进行m-1次 step=-1,temp=999999; for(j=1;j<=m;j++){//找出第一列中最短边 if(!visted[j]&&low[j]<temp){ temp=low[j];//存储最短边距离 step=j;//推进到下一个点 } } if(step==-1){//没有可以走的点,没办法走下一步 cout<<"?"<<endl; break;//退出 } else{//加入这个点的善后处理 visted[step]=1; sum+=temp; for(int k=1;k<=m;k++){ if(!visted[k]&&num[step][k]<low[k]){//在即将要走的点中更新最短距离集 low[k]=num[step][k]; } } } } if(step!=-1){ cout<<sum<<endl; } } return 0;}
发表评论 共有条评论
用户名: 密码:
验证码: 匿名发表