UVA908[Re-connecting Computer Sites]题解-Toy模板网

这篇具有很好参考价值的文章主要介绍了UVA908[Re-connecting Computer Sites]题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

原题

1.题意分析

题意就是给你很多组数，对于每组数，有三组小数据。第一组小数据先输入一个n表示顶点数，然后再输入n-1条边表示初始边数。其它组小数据先输入一个数k，表示增加的边的数量，然后再输入k条边，表示增加的边。在输入第二组小数据时，要先把边清空，重新输入，但是边的数量不变。

2.做法

题意不难理解，说白了就是最小生成树的板子题。很明显，对于每组数，可以分为两组大数据。第一组小数据是一组大数据；第二组和第三组小数据可以分为一组大数据。对于每组大数据，求出最小生成树，再把数据清空，再求一遍。就是最终的正解了

3.关于最小生成树

板子

板子题原题

kruskal最小生成树算法的详细分析

注意输入的换行，换行卡了我10分钟

~~它终于来了~~文章来源地址https://www.toymoban.com/news/detail-674887.html

代码

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 1e5 + 100;

int parents[N];

struct edge
{
	int from, to, val;
}edges[N];

bool cmp(edge a, edge b)
{
	if(a.val != b.val)
	{
		return a.val < b.val;
	}else
	{
		return a.from > b.from;
	}
	return a.to > b.to;
}

int cnt = 0;
void add(int u, int v, int w)
{
	cnt++;
	edges[cnt].from = u;
	edges[cnt].to = v;
	edges[cnt].val = w;
}

int Find(int n)
{
	int last_find = n;
	while(true)
	{
		if(parents[n] == n || parents[n] == last_find)
		{
			return n;
		}
		last_find = n;
		n = parents[n];
	}
}

int kruskal(edge* edges, int points, int bian)
{
	int w = 0;
	int cur_cnt = 0;
	int ans = 0;
	sort(edges + 1, edges + bian + 1, cmp);
	while(cur_cnt < points-1)
	{
		w++;
		int node_1 = Find(edges[w].from);
		int node_2 = Find(edges[w].to);
		if(node_1 != node_2)
		{
			parents[Find(node_1)] = parents[Find(node_2)];
			ans += edges[w].val;
			cur_cnt++;
		}
//		cout << cur_cnt << " " << w << endl;
//		cout << ans << endl;
	}
	return ans;
}

void init(int n)
{
	cnt = 0;
	for(int i = 1;i <= n;i++)
	{
		parents[i] = i;
	}
}

int main()
{
	int ccnntt=0;
	int n;
	while(cin >> n)
	{
		if(ccnntt!=0){
			cout<<endl;
		}
		ccnntt++;
		init(n);
		for(int i = 1;i < n;i++)
		{
			int u, v, w;
			cin >> u >> v >> w;
			add(u, v, w);
		}
		cout << kruskal(edges, n, n - 1) << endl;
		
		init(n);
		int k;
		cin >> k;
		for(int i = 1;i <= k;i++)
		{
			int u, v, w;
			cin >> u >> v >> w;
			add(u, v, w);
		}
		int m;
		cin >> m;
		for(int i = 1;i <= m;i++)
		{
			int u, v, w;
			cin >> u >> v >> w;
			add(u, v, w);
		}
		cout << kruskal(edges, n, k + m) << endl;
	}
	
	return 0;	
}

到了这里，关于UVA908[Re-connecting Computer Sites]题解的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！