Algorithm
Problem link- https://www.spoj.com/problems/CSTREET/
CSTREET - Cobbled streets
The municipal chronicals of an unbelievable lordly major town in a land far, far away tell the following story:
Once upon a time the new crowned king Günther decided to visit all towns in his kingdom. The people of the unbelievable lordly major town expected that king Günther would like to see some of the most famous buildings in their town. For the lordly citizens it seemed neccessary that all streets in the town that the king would have to use had to be cobbled with stone. Unfortunately the unbelievable lordly major town had not much money at that time as they used most of their savings to erect the highest cathedral the world had ever seen.
Roumours were afloat that the real reason for their thriftiness was not that the town treasury was empty but that many people believed that king Günther came to the throne by deceiving his father king Erwin and that in his youth he made a pact with the devil. But anyway, the citizens of the unbelievable lordly major town decided to pave only as much streets as were absolutely necessary to reach every major building.
Can you help the citizens of the unbelievable lordly major town to find out which streets should be paved?
It might be usefull to know that all major buildings are either at the end of a street or at an intersection. In addition to that you can assume that all buildings are connected by the given streets.
Input
t [number of testcases (1 <= t <= 100)]
p [price to pave one furlong of street (positive integer)]
n [number of main buildings in the town (1 <= n <= 1000)]
m [number of streets in the town (1 <= m <= 300000)]
a b c [street from building a to building b with length c (lengths are given in furlong and the buildings are numbered from 1 to n)]
Output
For each testcase output the price of the cheapest possibility to reach all main buildings in the city on paved streets. You can assume that the result will be smaller than 2^32.
Example
Input: 1 2 5 7 1 2 1 2 3 2 2 4 6 5 2 1 5 1 3 4 5 2 3 4 3 Output: 12
Code Examples
#1 Code Example with C++ Programming
Code -
C++ Programming
#include <bits/stdc++.h>
#include <limits.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<int> vi;
#define MOD (ll)1000000007
#define pb push_back
#define EPS 1e-9
#define FOR(i,n) for(int i = 0;i < n; i++)
#define FORE(i,a,b) for(int i = a;i <= b; i++)
#define pi(a) printf("%d\n", a)
#define all(c) c.begin(), c.end()
#define tr(container, it) for(typeof(container.begin()) it = container.begin(); it != container.end(); it++)
#define gc getchar_unlocked
#define sdi(a, b) si(a);si(b)
#define io ios_base::sync_with_stdio(false);cin.tie(NULL);
#define endl '\n'
template <typename T> T gcd(T a, T b){return (b==0)?a:gcd(b,a%b);}
template <typename T> T lcm(T a, T b){return a*(b/gcd(a,b));}
template <typename T> T mod_exp(T b, T p, T m){T x = 1;while(p){if(p&1)x=(x*b)%m;b=(b*b)%m;p=p>>1;}return x;}
template <typename T> T invFermat(T a, T p){return mod_exp(a, p-2, p);}
template <typename T> T exp(T b, T p){T x = 1;while(p){if(p&1)x=(x*b);b=(b*b);p=p>>1;}return x;}
void si(int &x){
register int c = gc();
x = 0;
int neg = 0;
for(;((c<48 || c>57) && c != '-');c = gc());
if(c=='-') {neg=1;c=gc();}
for(;c>47 && c<58;c = gc()) {x = (x<<1) + (x<<3) + c - 48;}
if(neg) x=-x;
}
const int MAXN = 3e5+5;
int parent[MAXN], buildings, streets;
pair<ll, pair<int, int> > p[MAXN];
void initialize(){
for(int i = 0;i <= buildings; i++){
parent[i] = i;
}
}
int root(int x){
while(parent[x] != x){
parent[x] = parent[parent[x]];
x = parent[x];
}
return x;
}
void union1(int x, int y){
int root_a = root(x);
int root_b = root(y);
parent[root_a] = root_b;
}
ll kruskal(pair<ll, pair<int, int> > p[]){
int x, y;
ll cost, minimumCost = 0;
for(int i = 0;i < streets; i++){
x = p[i].second.first;
y = p[i].second.second;
cost = p[i].first;
//check if the selected edge makes a cycle or not.
if(root(x)!=root(y)){
minimumCost += cost;
union1(x, y);
}
}
return minimumCost;
}
int main(){
io;
int t;
cin>>t;
while(t--){
int price;
cin>>price>>buildings>>streets;
ll weight, cost, minimumCost;
initialize();
int x,y;
for(int i = 0;i < streets; i++){
cin>>x>>y>>weight;
p[i] = make_pair(weight, make_pair(x, y));
}
sort(p, p+streets);
minimumCost = kruskal(p);
cout<<minimumCost*(ll)price<<endl;
}
return 0;
}Input
2
5
7
1 2 1
2 3 2
2 4 6
5 2 1
5 1 3
4 5 2
3 4 3
Output
Demonstration
SPOJ Solution-Cobbled streets-Solution in C, C++, Java, Python