toj3073 Country road prim算法 典型题

发布时间:2016-12-7 22:29:05 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"toj3073 Country road prim算法 典型题",主要涉及到toj3073 Country road prim算法 典型题方面的内容,对于toj3073 Country road prim算法 典型题感兴趣的同学可以参考一下。

要进行一些初始化的处理~ //toj3073 Country road prime算法 典型题 #include<iostream> #include<memory.h> #define MAX 200000 using namespace std; int map[1005][1005]; int visit[1005]; int dist[1005],i,j,k,m,n; int prime() { int sum,min,pos; sum=0; memset(visit,0,sizeof(visit));//初始化visit visit[1]=1; for(i=1;i<=n;i++) dist[i]=map[1][i];//dist中存map中1到所有点的值 for(i=0;i<n;i++)//找出生成树集合点集相连最小权值的边 { min=MAX; for(j=1;j<=n;j++) if(visit[j]==0&&dist[j]<min) { pos=j; min=dist[j]; } //if(min==MAX) return -1;//找不到 visit[pos]=1;//pos点加入最小生成树集合 //sum+=min; for(j=1;j<=n;j++)//更新dist数组 { if(visit[j]==0&&map[pos][j]<dist[j]) dist[j]=map[pos][j]; } } for(i=1;i<=n;i++) { sum+=dist[i]; if(dist[i]==MAX)return -1; } return sum; } int main() { int cases; int s,e,v; cin>>cases; while(cases--) { cin>>n>>m>>k;//n条路,m个已修路,k个待修路 for(i=1;i<=n;i++) { for(j=1;j<=n;j++) if(i==j)map[i][j]=0;//自己到自己是通的 else map[i][j]=MAX;//初始化一开始都不通 }//init for(i=1;i<=m;i++) { cin>>s>>e;//s到e点修了路 map[s][e]=map[e][s]=0;//通了,花费0 } for(i=1;i<=k;i++) { cin>>s>>e>>v;//s到e 花费为v map[s][e]=map[e][s]=v;//通了 } cout<<prime()<<endl; } return 0; }

上一篇:Oracle 获取当前年、月、日
下一篇:Android 键盘驱动移植呆板手册(从kernel到Java应用层简单描述)

相关文章

相关评论