# 題目: UVa 11631 - Dark Roads

# 題目說明

一個城市裡有很多的路相連，道路上每一公尺，路燈的cost為1
找出每個路口能到任意其他路口，最多能減少多少cost的路燈
(整條路每一公尺有一個路燈)

---

INPUT:
每筆測資第一行有兩個整數m和n

1. m代表路口的數量
2. n代表道路的數量

接下來有n行，每行有三個整數x、y、z
代表x與y路口間有一條長z的路

---

OUTPUT:
輸出最多能減少多少cost的路燈

# 解題方法

先將所有路口的編號及cost存入edge
接著以kruskcal演算法，先對距離進行sort，再用union_find演算法判斷是否可連通
以總cost，每次減掉最短路徑的cost，即為答案

# 參考程式碼

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;

vector< tuple<int, int, int> > edge;
vector<int> parents;
vector<int> ranks;
int cost;

bool cmp(tuple<int, int, int> r1, tuple<int, int, int> r2)
{
	return get<2>(r1) < get<2>(r2);
}

bool union_find(int r1, int r2)
{
	// find root of r1 and r2
	while (r1 != parents[r1]) r1 = parents[r1];
	while (r2 != parents[r2]) r2 = parents[r2];

	// circle
	if (r1 == r2) return false;

	if (ranks[r1] > ranks[r2]) parents[r2] = r1;
	else if (ranks[r2] > ranks[r1]) parents[r1] = r2;
	else parents[r2] = r1, ++ranks[r1];

	return true;
}

int kruskcal(int m)
{
	sort(edge.begin(), edge.end(), cmp);

	int side = 0;
	for (auto& [r1, r2, w] : edge)
	{
		if (side == m - 1) break;

		// union find algorithm
		if (union_find(r1, r2))
		{
			cost -= w;
			++side;
		}
	}

	return cost;
}

int main()
{
	// fast io
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int m, n;
	while (cin >> m >> n, m && n)
	{
		// init
		edge.clear();
		parents.clear();
		ranks.assign(m, 0);
		for (int i = 0; i < m; ++i) parents.emplace_back(i);
		cost = 0;

		// store roads in edges
		while (n--)
		{
			int x, y, z;
			cin >> x >> y >> z;
			cost += z;
			edge.push_back({ x, y, z });
		}

		// kruskcal algorithm
		cout << kruskcal(m) << "\n";
	}

	return 0;
}

# 參考資料

https://www.larrysprognotes.com/UVa%20-%2011631/