时间限制: 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
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
struct node{
int from;
int to;
int longlist;
}edge[];
int cnt=,n,map[][],l[][],dis[],vis[],s[],u[];
int main()
{
scanf("%d",&n); memset(dis,0x3f,sizeof dis ); for(int i=;i<=n;i++)
for(int j=;j<=n;j++)
scanf("%d",&map[i][j]); int k=;
dis[]=;// dis[]数组存储从1到该点的最小距离 for(int i=;i<=n;i++)
{
k=;
for(int j=;j<=n;j++)
if(vis[j]==&&dis[k]>dis[j])//vis[j]==0 未访问过
k=j;// dis[k]>dis[j] 选取最小的点进行更新
s[i]=k;// s 存储第几条边
vis[k]=;// 标记该 点已用
// 选取最小的蓝点 将其标记为白点
for(int j=;j<=n;j++)
if(vis[j]==&&dis[j]>map[j][k])
{
dis[j]=map[j][k];
// Prim小模板
if(j<k)
l[j][]=j,l[j][]=k;
else l[j][]=k,l[j][]=j;
}
}
int tot=,sum=;
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 }
printf("%d\n",tot);
for(int i=;i<=tot;i++)
55 printf("%d %d\n",l[u[i]][0],l[u[i]][1]);
printf("%d\n",sum);
return ;
}
思路：见代码中的思路，还有题目给定的已经连接的线路并不一定在最小生成树中，（题目没让你必须用这些啊！为何不选个小的！~）标红段代码务必好好理解
此题Prim算法好打，但是我觉得存边，输出边还是有一定难度的