【9005】最短网络agrinet

Time Limit: 1 second

Memory Limit: 256 MB

问题描述

农民约翰被选为他们镇的镇长！他其中一个竞选承诺就是在镇上建立起互联网，并连接到所有的农场。当然，他需要你的帮助。约翰

已经给他的农场安排了一条高速的网络线路，他想把这条线路共享给其他农场。为了用最小的消费，他想铺设最短的光纤去连接

所有的农场。你将得到一份各农场之间连接费用的列表，你必须找出能连接所有农场并所用光纤最短的方案。每两个农场间的距

离不会超过100000。　

Input

第一行：农场的个数，N（3<=N<=100）。

第二行..结尾: 后来的行包含了一个N*N的矩阵,表示每个农场之间的距离。理论上，他们是N行，每行由N个用空格分隔的数组成，实

际上，他们限制在80个字符，因此，某些行会紧接着另一些行。当然，对角线将会是0，因为不会有线路从第i个农场到它本身。

Output

只有一个输出，其中包含连接到每个农场的光纤的最小长度。

Sample Input

Sample Output

【题解】

这是一道裸的最小生成树。在读入的时候用两层循环i和j,只有当j > i时才记录数据。否则不记录。因为这矩阵是沿着对角线对称的。只要读一边就好。因为用的是kruskal算法。所以要记录边的信息。用一个结构体来存储边的信息，然后用algorithm头文件中的sort函数直接对结构体进行排序即可。不要自己写快排了，浪费时间。

cmp函数（const 结构体名称 &a,const 结构体名称 &b）

if (a.w < b.w)

return 1;

return 0;

这样就可根据结构体的w进行从小到大排序。

【代码】

#include <cstdio>

#include <algorithm>

using namespace std; //用algorithm就一定要加这句 

struct edge //定义一个名为edge的结构体

{

	int x,y,w;

};

edge a[10000];

int n,tt,f[101],num = 0,co = 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].x = i;

						a[num].y = j;

						a[num].w = x;

					}

			}

}

int cmp(const edge & a,const edge & b) //比较函数  < 表示从小到大排序

{

	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].x,y = a[i].y;

			int r1 = findfather(x),r2 = findfather(y); //看这条边的两个点是否属于同一个集合

			if (r1!=r2) //如不在一个集合 则合并它们

				{

					f[r2] = r1;

					tt+=a[i].w; //然后累加和

					co++; //记录下找了多少条边

					if (co == n-1) //如果找了N-1条边就跳出程序。

						return;

				}

		}

}

void output_ans()

{

	printf("%d",tt);

}

int main()

{

	//freopen("F:\\rush.txt","r",stdin);

	input_data();

	sort(a+1,a+1+num,cmp);

	get_ans();

	output_ans();

	return 0;

}

巴特西

【9005】最短网络agrinet

Input

Output

Sample Input

Sample Output

最新文章

热门文章