首页 > 代码库 > Hdu 3371 Connect the Cities（最小生成树）
Hdu 3371 Connect the Cities（最小生成树）
地址：http://acm.hdu.edu.cn/showproblem.php?pid=3371
其实就是最小生成树，但是这其中有值得注意的地方：就是重边。题目没有告诉你两个城市之间只有一条路可走，所以两个城市之间可能有多条路可以走。
举例： 输入可以包含 1 2 3 // 1到2的成本为3
1 2 5 //1到2的成本为5
因此此时应选成本较低的路。
然后，已经连通的城市之间的连通成本为0。
这题用G++提交得到984ms的反馈，用C++提交则得到484ms的反馈。
很想知道这个时间差是怎么回事。
另外，这题一定还可以优化。
#include <iostream>#include <cstring>#include <cstdio>using namespace std;const int maxn = 500+10;int dis[maxn][maxn]; //存两地间的距离bool vis[maxn]; //是否已经加入树int temp[maxn];int shortP[maxn];const int INF = 65523655;int n,m,k;inline void input() //初始及输入{ cin>>n>>m>>k; int i,j; for(i=1;i<=n;i++) for(j=1;j<=n;j++) dis[i][j]=INF; int p,q,r; while(m--) { scanf("%d%d%d",&p,&q,&r); if( r<dis[p][q] ) //这一句保证存入的是两地间距离的最小值 dis[p][q]=dis[q][p]=r; } int t; memset(temp,0,sizeof(temp)); while(k--) { scanf("%d",&t); for(i=1;i<=t;i++) scanf("%d",&temp[i]); for(i=1;i<=t;i++) for(j=i+1;j<=t;j++) dis[ temp[i] ][ temp[j] ]=dis[ temp[j] ][ temp[i] ]=0; } memset(vis,false,sizeof(vis)); for(i=1;i<=n;i++) shortP[i]=INF;}inline int span() //求最低成本{ int cost=0; int pos=1,k; int count=0; int i,minC=INF; vis[1]=true; while(count<n-1) //判断最小生成树是否已经完成 { for(i=1;i<=n;i++) if( !vis[i] && shortP[i] > dis[pos][i] ) shortP[i]=dis[pos][i]; k=-1; minC=INF; for(i=1;i<=n;i++) if( !vis[i] && minC > shortP[i] ) { minC=shortP[i]; k=i; } if(k==-1) return -1; //判断是否还可以再把一个城市加进来 cost += shortP[k]; vis[k]=true; pos=k; count++; } return cost;}int main(){ int T; while(cin>>T) { int flag; while(T--) { input(); flag = span(); cout<<flag<<endl; } } return 0;}
Hdu 3371 Connect the Cities（最小生成树）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。