Algorithm
problem Link : https://onlinejudge.org/index.php?option=onlinejudge&Itemid=8&page=show_problem&problem=1541
In order to prepare the “The First National ACM School Contest” (in 20??) the major of the city decided to provide all the schools with a reliable source of power. (The major is really afraid of blackoutsJ). So, in order to do that, power station “Future” and one school (doesn’t matter which one) must be connected; in addition, some schools must be connected as well. You may assume that a school has a reliable source of power if it’s connected directly to “Future”, or to any other school that has a reliable source of power. You are given the cost of connection between some schools. The major has decided to pick out two the cheapest connection plans – the cost of the connection is equal to the sum of the connections between the schools. Your task is to help the major — find the cost of the two cheapest connection plans. Input The Input starts with the number of test cases, T (1 < T < 15) on a line. Then T test cases follow. The first line of every test case contains two numbers, which are separated by a space, N (3 < N < 100) the number of schools in the city, and M the number of possible connections among them. Next M lines contain three numbers Ai , Bi , Ci , where Ci is the cost of the connection (1 < Ci < 300) between schools Ai and Bi . The schools are numbered with integers in the range 1 to N. Output For every test case print only one line of output. This line should contain two numbers separated by a single space – the cost of two the cheapest connection plans. Let S1 be the cheapest cost and S2 the next cheapest cost. It’s important, that S1 = S2 if and only if there are two cheapest plans, otherwise S1 < S2. You can assume that it is always possible to find the costs S1 and S2.
Sample Input 2 5 8 1 3 75 3 4 51 2 4 19 3 2 95 2 5 42 5 4 31 1 2 9 3 5 66 9 14 1 2 4 1 8 8 2 8 11 3 2 8 8 9 7 8 7 1 7 9 6 9 3 2 3 4 7 3 6 4 7 6 2 4 6 14 4 5 9 5 6 10
Sample Output 110 121 37 37
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <bits/stdc++.h>
using namespace std;
int fastio() { ios_base::sync_with_stdio(false); cout << fixed << setprecision(10); cin.tie(nullptr); return 0; }
int __fastio = fastio();
struct UF {
vector<int> pars;
int cnt;
UF(int N):cnt(N) {
pars.assign(N, 0);
for(int i=0;i < N;i++) pars[i] = i;
}
bool connected(int a, int b) {
return find(a) == find(b);
}
int find(int x) {
return pars[x] == x ? x : pars[x] = find(pars[x]);
}
void join(int a, int b) {
if(connected(a, b)) return;
a = find(a), b = find(b);
pars[b] = a;
cnt--;
}
};
void solve() {
int n, m;
cin >> n >> m;
vector<tuple < int, int, int>> edges;
for(int i=0;i < m;i++) {
int a, b, c;
cin >> a >> b >> c;
a--; b--;
edges.emplace_back(c, a, b);
}
sort(all(edges));
vector<int> mstIndex;
int mst1 = 0, mst2 = 1e9;
UF uf(n);
for(int i=0;i < m;i++) {
auto&[c,a,b] = edges[i];
if(uf.connected(a,b)) continue;
mst1 += c;
mstIndex.push_back(i);
uf.join(a, b);
}
for(int b : mstIndex) {
uf = UF(n);
int cost = 0;
for(int i=0;i < m;i++) {
if(b == i) continue;
auto&[c,a,b] = edges[i];
if(uf.connected(a,b)) continue;
cost += c;
uf.join(a, b);
}
if(uf.cnt == 1) mst2 = min(mst2, cost);
}
cout << mst1 << " " << mst2 << "\n";
}
int main() {
int t=1;
cin >> t;
while(t--) {
solve(>;
}
}
Input
5 8
1 3 75
3 4 51
2 4 19
3 2 95
2 5 42
5 4 31
1 2 9
3 5 66
9 14
1 2 4
1 8 8
2 8 11
3 2 8
8 9 7
8 7 1
7 9 6
9 3 2
3 4 7
3 6 4
7 6 2
4 6 14
4 5 9
5 6 10
Output
37 37
Demonstration
UVA Online Judge solution - 10600-ACM Contest and Blackout - UVA Online Judge solution in C,C++,java