- আমাদের কে গ্রফল্যান্ডের শহরগুলির যে 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 ;)
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* 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; | |
} |
হ্যাপি কোডিং :D
Comments
Post a Comment