欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

UVA 10600 ACM Contest and Blackout(次小生成树)

程序员文章站 2024-03-21 17:37:22
...

题目传送

次小生成树模板题:
先求出最小生成树,然后再遍历所有没用过的边,加上去,这时会形成一个环,去掉环中的第二大的边,更新结果。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = 110;
const int maxm = maxn * maxn;

int n, m;
int par[maxn];
int maxd[maxn][maxn];
int used[maxm];
vector<int> G[maxn];

struct edgs {
	int from, to, dis;
	bool operator < (const edgs& a) const {
		return dis < a.dis;
	}
}edg[maxm];

void init() //初始化
{
	for (int i = 1; i <= n; i++) {
		par[i] = i;
		G[i].clear();
		G[i].push_back(i); //卡了好久,很关键的一步
		for (int j = 1; j <= n; j++) maxd[i][j] = 0;	
	}
	memset(used, 0, sizeof(used));
}

int find(int x)
{
	return par[x] == x ? x : par[x] = find(par[x]);
}

int main(void)
{
	int t;
	cin >> t;
	while (t--) {
		cin >> n >> m;
		init();
		for (int i = 1; i <= m; i++) {
			int a, b, c;
			cin >> a >> b >> c;
			edg[i].from = a;
			edg[i].to = b;
			edg[i].dis = c;
		}
		sort(edg + 1, edg + m + 1);
		int ans = 0, cnt = 0;
		for (int i = 1; i <= m; i++) {
			int rf = find(edg[i].from);
			int rt = find(edg[i].to);
			if (rf == rt) continue;
			ans += edg[i].dis;
			used[i] = 1;
			for (int j = 0; j < G[rf].size(); j++) {
				for (int l = 0; l < G[rt].size(); l++) { //记录两点间的最长边
					maxd[G[rf][j]][G[rt][l]] = maxd[G[rt][l]][G[rf][j]] = edg[i].dis;
				}
			}
			par[rf] = rt;
			for (int j = 0; j < G[rf].size(); j++) G[rt].push_back(G[rf][j]); //合并两个连通块
			if (++cnt == n - 1) break;
		}
		cout << ans << " ";
		int res = 0x3f3f3f3f;
		for (int i = 1; i <= m; i++) {
			if (!used[i]) {
				res = min(res, ans + edg[i].dis - maxd[edg[i].from][edg[i].to]); //更新结果
			} 
		}
		cout << res << endl;
	}
	return 0;
}
相关标签: 生成树