[ UVa ] 11228 - Transportation system

• আমাদের কে গ্রফল্যান্ডের শহরগুলির যে co-ordinate দেয়া থাকবে  তাদের সবগুলি থেকে সবগুলির দূরত্ব বের করে সেটা কে ওয়েট ধরে একটা গ্রাফ বানাতে হবে । 
• এই গ্রাফ থেকে MST বের করেত  হবে । 
• আমাদের মূল গ্রাফ থেকে MST বের করার সময় যখন প্রতিবার একটা করে নতুন এজ নিব তখন চেক করতে হবে নতুন এজটার ওয়েট আমাদের Threshold ( r )  থেকে বড় কি না ? 
• যদি সেটা r থেকে বড় হয় তবে সেই এজটা ওয়েট rail roads extension এ যোগ করতে হবে । আর যদি সেটা r থেকে ছোট হয় তবে সেটা state roads extension এ যোগ করতে হবে । 
• মোট states সংখ্যা = mst তে  মোট node সংখ্যা - মোট এজ সংখ্যা [ rail road এজ বাদে ] 
• প্রিন্ট Extension rounded to the nearest integer ;) 

কোড : 

	/**
	* Problem : 11228 - Transportation system.
	* Verdict : Accepted.
	* Time : 0.090 ms.
	* Writer : Mehadi Hasan Menon.
	* Date : 03.01.17.
	**/
	#include <iostream>
	#include <algorithm>
	#include <vector>
	#include <cmath>
	using namespace std;
	typedef pair <int, int> ii;
	typedef vector <ii> vii;
	const int mx = 1005;
	int father[mx * mx];
	struct edge {
	int u, v;
	double w;
	bool operator < (const edge &p) const {
	return w < p.w;
	}
	};
	int find_father(int r)
	{
	if(father[r] == r) {
	return r;
	}
	father[r] = find_father(father[r]);
	return father[r];
	}
	double get_distance(ii point1, ii point2)
	{
	double a = point1.first - point2.first;
	double b = point1.second - point2.second;
	return sqrt((a)* (a) + (b) * (b));
	}
	int main()
	{
	freopen("input.txt", "r+", stdin);
	int tc, n, r, u, v;
	scanf("%d", &tc);
	for(int t = 1; t <= tc; t++)
	{
	scanf("%d %d", &n, &r);
	int x, y;
	vii city;
	// store all the points.
	for(int i = 0; i < n; i++) {
	scanf("%d %d", &x, &y);
	city.push_back(ii(x, y));
	}
	vector <edge> edge_list;
	// make a graph using all given coordinate.
	// weight is distance between two points.
	for(int i = 0; i < n; i++)
	{
	for(int j = i + 1; j < n; j++)
	{
	double dis = get_distance(city[i], city[j]);
	edge data;
	data.u = i;
	data.v = j;
	data.w = dis;
	edge_list.push_back(data);
	}
	}
	// make set
	for(int i = 0; i <= n; i++) {
	father[i] = i;
	}
	sort(edge_list.begin(), edge_list.end());
	int sz = edge_list.size();
	int cnt;
	double states_cost, rail_road_cost;
	states_cost = rail_road_cost = cnt = 0;
	for(int i = 0; i < sz; i++)
	{
	edge new_edge = edge_list[i];
	int u = find_father(new_edge.u);
	int v = find_father(new_edge.v);
	double w = new_edge.w;
	if(u != v)
	{
	father[v] = u;
	if(w <= r) {
	cnt += 1;
	states_cost += w;
	}
	else {
	rail_road_cost += w;
	}
	}
	}
	// imagine as number of connected component without rail road edges:)
	int total_states = n - cnt;
	printf("Case #%d: %d %.lf %.lf\n", t, total_states, states_cost, rail_road_cost);
	}
	return 0;
	}

view raw 11228.cpp hosted with ❤ by GitHub

হ্যাপি কোডিং :D