首页 > 代码库 > Codevs 1003 电话连线
Codevs 1003 电话连线
时间限制: 1 s 空间限制: 128000 K 题目等级 : 黄金 Gold
题目描述 Description
一个国家有n个城市。若干个城市之间有电话线连接,现在要增加m条电话线(电话线当然是双向的了),使得任意两个城市之间都直接或间接经过其他城市有电话线连接,你的程序应该能够找出最小费用及其一种连接方案。
输入描述 Input Description
输入文件的第一行是n的值(n<=100).
第二行至第n+1行是一个n*n的矩阵,第i行第j列的数如果为0表示城市i与城市j有电话线连接,否则为这两个城市之间的连接费用(范围不超过10000)。
输出描述 Output Description
输出文件的第一行为你连接的电话线总数m,第二行至第m+1行为你连接的每条电话线,格式为i j,(i<j), i j是电话线连接的两个城市。输出请按照Prim算法发现每一条边的顺序输出,起始点为1.
第m+2行是连接这些电话线的总费用。
样例输入 Sample Input
5
0 15 27 6 0
15 0 33 19 11
27 33 0 0 17
6 19 0 0 9
0 11 17 9 0
样例输出 Sample Output
2
1 4
2 5
17
数据范围及提示 Data Size & Hint
n<=100
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 using namespace std; 5 struct node{ 6 int from; 7 int to; 8 int longlist; 9 }edge[5000]; 10 int cnt=0,n,map[100][100],l[102][2],dis[110],vis[102],s[101],u[101]; 11 int main() 12 { 13 scanf("%d",&n); 14 15 memset(dis,0x3f,sizeof dis ); 16 17 for(int i=1;i<=n;i++) 18 for(int j=1;j<=n;j++) 19 scanf("%d",&map[i][j]); 20 21 int k=0; 22 dis[1]=0;// dis[]数组存储从1到该点的最小距离 23 24 for(int i=1;i<=n;i++) 25 { 26 k=0; 27 for(int j=1;j<=n;j++) 28 if(vis[j]==0&&dis[k]>dis[j])//vis[j]==0 未访问过 29 k=j;// dis[k]>dis[j] 选取最小的点进行更新 30 s[i]=k;// s 存储第几条边 31 vis[k]=1;// 标记该 点已用 32 // 选取最小的蓝点 将其标记为白点 33 for(int j=1;j<=n;j++) 34 if(vis[j]==0&&dis[j]>map[j][k]) 35 { 36 dis[j]=map[j][k]; 37 // Prim小模板 38 if(j<k) 39 l[j][0]=j,l[j][1]=k; 40 else l[j][0]=k,l[j][1]=j; 41 } 42 } 43 int tot=0,sum=0; 44 for(int i=1;i<=n;i++) 45 { 46 if(dis[s[i]]!=0) 47 { 48 tot++; 49 u[tot]=s[i]; 50 sum+=dis[s[i]]; 51 } 52 } 53 printf("%d\n",tot); 54 for(int i=1;i<=tot;i++) 55 printf("%d %d\n",l[u[i]][0],l[u[i]][1]); 56 printf("%d\n",sum); 57 return 0; 58 }
思路:见代码中的思路,还有题目给定的已经连接的线路并不一定在最小生成树中,(题目没让你必须用这些啊!为何不选个小的!~)标红段代码务必好好理解
此题Prim算法好打,但是我觉得存边,输出边还是有一定难度的
Codevs 1003 电话连线
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。