题目：
时间限制: 1 s
空间限制: 128000 KB
题目等级 : 黄金 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
思路：
先将起始点加到最小生成树中，然后以起始点更新队列中的点的距离。然后在队列中找终点不在树中的最短边，将该边的终点加入到最小生成树中，再以该点更新队列，重复该步骤直至找出n-1条边然后退出循环，即得到最小生成树。
代码：
#include#include using namespace std;const int size = 1e5+10;//链式向前星struct Edge{ int to; int len; int next;};struct Edge edges[size];int head[size];int cnt;int que[2][size];//当前所有点距最小生成树的最短距离和起点(便于最后输出)bool marked[size];//标记已在最小生成树中的点//用于存答案int ans;int add[2][size];int count;void init()//初始化{ cnt = 0; ans = 0; count = 0; for(int i = 0; i < size; i++) { head[i] = -1; que[0][i] = 0x3f3f3f3f; marked[i] = false; }}void addEdge(int u, int v, int w){ edges[cnt].to = v; edges[cnt].len = w; edges[cnt].next = head[u]; head[u] = cnt++;}void prim(int n){ //加入起始点 marked[0] = true; que[0][0] = 0; for(int i = head[0]; i != -1; i=edges[i].next) { if(!marked[edges[i].to] && edges[i].len < que[0][i]) { que[0][i] = edges[i].len; que[1][i] = 0; } } for(int i = 0; i < n-1; i++)//只要循环找n-1条边就完成了 { int a, b;//起点，终点 int minlen = 0x3f3f3f3f; for(int j = 0; j < n; j++)//从que中找当前可达最短边 { if(!marked[j] && que[0][j] < minlen) { minlen = que[0][j]; a = que[1][j]; b = j; } } //将b加入最小生成树中 marked[b] = true; ans+=minlen; if(minlen != 0)//把权不为0的边的起点终点加入add数组中 { add[0][count] = a < b ? a : b; add[1][count] = a == add[0][count] ? b : a; count++; } //以新加入的b点更新que for(int j = head[b]; j != -1; j = edges[j].next) { if(!marked[edges[j].to] && edges[j].len < que[0][edges[j].to]) { que[0][edges[j].to] = edges[j].len; que[1][edges[j].to] = b; } } }}int main(){ init(); int n; int c; //输入 scanf("%d", &n); for(int i = 0; i < n; i++) { for(int j= 0; j < n; j++) { scanf("%d", &c); addEdge(i,j,c); } } prim(n); cout << count << endl; for(int i = 0; i < count; i++) printf("%d %d\n", add[0][i]+1, add[1][i]+1); cout << ans << endl; return 0;}