【wikioi】1003 电话连线

时间：2021-07-31 11:12:11

题目链接

算法： 最小生成树

PS：被卡过2天（中间的时间没去做）。日期：2013-09-13 13:49:47 ~ 2013-09-17 13:01:07

此题为基础题

刚开始学图论时只会用Kruskal+并查集，以为Kruskal和Prim差不多= =于是就用Kruskal来做这题，结果是不用说的

然后就学习了Prim，并在我之前的博文有介绍 最小生成树

题目描述：

一个国家有n个城市。若干个城市之间有电话线连接，现在要增加m条电话线（电话线当然是双向的了），使得任意两个城市之间都直接或间接经过其他城市有电话线连接，你的程序应该能够找出最小费用及其一种连接方案。
【wikioi】1003 电话连线

需要注意的是，输入中可能已经包含了电话线，所以要判断此电话线是否存在（输入中0表示有，故判断是否为true即可），存在就不予考虑。不会影响到算法。

CODE：

//最小生成树 Prim算法

//我没用到优先队列，是直接用暴力找出的= =

#include <iostream>

#include <algorithm>

using namespace std;

const int MAXN = 105;

const int INF = 2147483647;

int i, j, n;

long long ans = 0;

int edge[MAXN][MAXN], key[MAXN], p[MAXN], vis[MAXN] = {0}, //edge表示存的边 key表示权值，p表示父亲，vis表示是否已经存在已生成的树中

	f[MAXN], l[MAXN], m = 0; //f表示头，右边表示尾

int main()

{

	cin >> n;

	for(i = 1; i <= n; i++)for(j = 1; j <= n; j++) cin >> edge[i][j];

	for(i = 1; i <= n; i++) key[i] = INF;

	key[1] = 0; //

	p[1] = 1;

	int Mini, Min;

	for(i = 0; i < n; i++) //之需要加最多n条边，故循环n次

	{

		Min = INF;

		for(j = 1; j <= n; j++) if(!vis[j] && key[j] < Min){Mini = j; Min = key[j];} //找key值最小的点，即与树相邻的节点的最小权值边

		vis[Mini] = 1; //设置访问过，即生成树已连接Mini这个节点

		ans += key[Mini];

		if(key[Mini])

		{

			f[m] =   min(p[Mini], Mini); //字典序的边

			l[m++] = max(p[Mini], Mini); //同上

		}

		for(j = 1; j <= n; j++) //伪松弛，更新树临边节点的key值并维护p域

			if(!vis[j] && edge[Mini][j] < key[j])

			{key[j] = edge[Mini][j]; p[j] = Mini;}

	}

	cout << m << endl;

	for(i = 0; i < m; i++) cout << f[i] << ' ' << l[i] << endl;

	cout << ans;

	return 0;

}

相关文章