1092 演算法

題目說明

The ACM kingdom has n cities, numbered from 0 to n − 1. An (unordered) pair (i, j) ∈ {0, 1, . . . , n − 1}² of distinct cities is said to be linkable if we are able to build a road linking i and j. It is guaranteed that if we build a road between i and j for all linkable pairs (i, j) ∈ {0, 1, . . . , n − 1}², then any two distinct cities will be reachable (via one or more roads) from each other. For every linkable pair (i, j) ∈ {0, 1, . . . , n − 1}², denote by ci,j ≥ 0 the cost of building a road between i and j. Mr. Smart wants to build roads with the minimum product of costs subject to every city being reachable from every other city. Please help him.

Input

Each test case begins with n and then the number of linkable pairs. Every linkable pair (i, j) ∈ {0, 1, . . . , n − 1}² is specified by i, j and ci,j , in that order. Furthermore, any two consecutive integers are separated by whitespace character(s). The last test case is “0 0”, which shall not be processed.

Output

Do the following for each test case: Denoting by C the minimum product of costs subject to every city being reachable from every other city, please output the remainder of the division of C by 65537, i.e., C mod 65537.

Technical Specification

  1. There are at most 10 test cases.
  2. 2 ≤ n ≤ 500.
  3. There are at most 25000 linkable pairs.
  4. For every linkable pair (i, j) ∈ {0, 1, . . . , n − 1}², ci,j ∈ {0, 1, . . . , 999}.

解題思路

according to Kruskal’s algorithm to slove the problem.

參考解法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct e
{
	int v1;
	int v2;
	//bool check = false;
	int cost;
};

bool compare(e a, e b)
{
	return a.cost < b.cost;
}

long long int MST(vector <e>& g, vector <bool>& check, int v)
{
	sort(g.begin(), g.end(), compare);

	vector <int> father;
	father.resize(v);
	for (int i = 0; i < father.size(); i++)
	{
		father[i] = i;
	}
	vector <int> son;
	son.resize(v);
	for (int i = 0; i < son.size(); i++)
	{
		son[i] = 1;
	}

	int j = 0;
	long long int ans = 0;
	bool one = true;

	for (int i = 0; i < g.size() && j < v; i++)
	{
		int x = g[i].v1;
		int y = g[i].v2;

		while (x != father[x])
		{
			x = father[x];
		}
		while (y != father[y])
		{
			y = father[y];
		}

		if (x != y)
		{
			if (son[x] >= son[y])
			{
				father[y] = x;
				son[x] += son[y];
			}
			else
			{
				father[x] = y;
				son[y] += son[x];
			}
			
			if (one)
			{
				ans += g[i].cost;
				one = false;
				j++;
			}
			else
			{
				ans *= g[i].cost;
				ans %= 65537;
				j++;
			}
		}
	}
	
	return ans;
}

int main()
{
	int v, edge;

	while (cin >> v >> edge)
	{
		if (v == 0 && edge == 0)
		{
			break;
		}

		vector <e> g;
		vector <bool> check;
		check.resize(v);

		for (int i = 0; i < check.size(); i++)
		{
			check[i] = false;
		}

		for (int i = 0; i < edge; i++)
		{
			e temp;
			cin >> temp.v1 >> temp.v2 >> temp.cost;
			g.push_back(temp);
		}

		cout << MST(g, check, v) << endl;
		cout << endl;
	}

	return 0;
}