【9004】&&【7010】最优布线问题

Time Limit: 1 second
Memory Limit: 256 MB

问题描述
学校有n台计算机，为了方便数据传输，现要将他们用数据线连接起来。两台计算机被连接起来是指他们之间有数据线相连。由于计
算机所处的位置不同，因此不同的两台计算机的连接费用往往不同。
当然，如果将任意两条计算机都用数据线连接起来，费用将是相当庞大的。为了节省费用，我们采用数据间接传输手段，机一台计算
机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的相连。
现在由你负责连接这些计算机，你的任务是是任意两台计算机都联通（不管是间接的或是直接的）。　

Input

输入文件名为wire.in，第一行为整数n（2<=n<=100），表示计算机数目。此后的n行，每行n个整数。第x+1行y列的整数表示直接连
接第x台计算机和第y台计算机的费用。

Output

输出文件名为wire.out，一个整数，表示最小的连接费用。
（注：表示连1和2，2和3，费用为2）

Sample Input

Sample Output

【题解】

这题是用来练最小生成树的做法的。

我写了注释。算法的实现原理，可以去找书自己看。

【代码】

法一,克鲁斯卡尔算法

#include <cstdio>
#include <algorithm>

using namespace std;

struct edge
{
	int fr,to,w;	
};

edge a[10000];
int n,su,num,f[101],nn = 0;

void input_data()
{
	scanf("%d",&n);
	for (int i = 1;i <= n;i++) //这是并查集的初始化 每个节点指向它本身。 
		f[i] = i;
	for (int i = 1;i <= n;i++)
		for (int j = 1;j <= n;j++) //读入一个n*n的矩阵。但是有一半是没有用的，是无向图。 
			{
				int x;
				scanf("%d",&x);
				if (j > i) //只要读取j > i的那一部分矩阵就可以了 
					{
						num++;
						a[num].fr = i; //记录下这条边的信息。 
						a[num].to = j;
						a[num].w = x;
					}	
			}
}

int cmp(const edge & a,const edge &b) //这是对比函数 return 1表示要按照这样顺序排 
{
	if (a.w < b.w) return 1;
	return 0;	
}

int findfather(int x) //找根节点 
{
	if (f[x] != x)
		f[x] = findfather(f[x]);
	return f[x];
}

void get_ans() //来累加边 
{
	for (int i = 1;i <= num;i++) //对num条边都进行试探 
		{
			int x = a[i].fr,y = a[i].to;
			int r1 = findfather(x),r2 = findfather(y);
			if (r1 != r2) //如果这条边的两个点连接着不同的区域 
				{
					nn++;
					f[r2] = r1; //则合并起来 
					su += a[i].w;
					if (nn == n-1) //只要有N-1条边就可以宣告结束了。 
						return;
				}
		}
}

void output_ans()
{
	printf("%d",su);
}

int main()
{
	//freopen("F:\rush.txt","r",stdin);
	input_data();
	sort(a+1,a+1+num,cmp); //从1开始，下标为num+1结束。 
	get_ans();
	output_ans();	
	return 0;
}

法二，普里姆算法

#include <cstdio>
#include <cstring>

int next[10000],first[101],to[10000],num = 0,su,n,w[10000],dis[101],mi;
bool bo[101];

void input_data()
{
	scanf("%d",&n);
	for (int i = 1;i <= n;i++)
		for (int j = 1; j<= n;j++)
			{
				int x;
				scanf("%d",&x);
				if (i!=j) //可以写成 j > i，因为有一半的信息无用 
					{
						num++;
						next[num] = first[i]; //用邻接表的方式存储边的信息 
						to[num] = j;
						w[num] = x;
						first[i] = num;
					}
			}
					
}

void get_ans()
{
	memset(bo,false,sizeof(bo)); //一开始所有的数字都未加入MST 
	for (int i = 1;i <= n;i++) //扩展i节点所需要的费用都设为正无穷 
		dis[i] = 2100000000 / 3;
	dis[1] = 0; //从任意一个点开始进行MST的构造 
	for (int i = 1;i <= n+1;i++) //n+1随便写的。因为循环内有终止的方法 
		{
			mi = 2100000000 / 3;//这是为了获取dis中的最小值 
			int k = -1;
			for (int j = 1;j <= n;j++) //找一遍最小值 
				if (dis[j] < mi && !bo[j]) //一定要没有加入MST的点 
					{
						mi = dis[j];
						k = j;	
					}
			if (k == -1) //如果没找到就结束 
				break;
			bo[k] = true; //记录这个点加入MST 
			su += dis[k]; //累加和 
			int temp = first[k]; //查看这个点的出度 
			while (temp!=0)
				{
					int t = to[temp];
					if (dis[t] > w[temp]) //尝试更新扩展到t节点所需要的最小花费 
						dis[t] = w[temp];
					temp = next[temp];	
				}
		}
}

void output_ans()
{
	printf("%d",su);	
}

int main()
{
	//freopen("F:\rush.txt","r",stdin);
	input_data();
	get_ans();
	output_ans();
	return 0;
}