算法： 最小生成树

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

此题为基础题

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

然后就学习了Prim，并在我之前的博文有介绍 

题目描述：

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

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

CODE：

//最小生成树 Prim算法//我没用到优先队列，是直接用暴力找出的= =#include 
    
     #include 
     
      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;}