Skip to main content

[ 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

Comments

Popular posts from this blog

উবুন্টুতে রুট পাসওয়ার্ড ভুলে তা রিকভার করার উপায় ।

যদি কেউ রুট পাসওয়ার্ড ভুলে যান তাহলে নিচের কাজ গুলো করে নতুন পাসওয়ার্ড সেট করতে পারবেন: প্রথমে পিসি রিস্টার্ট দিন । দিয়ে UP/DOWN করে kernel version সিলেক্ট করে e চাপুন । ব্ল্যাক Screen আসবে এবার একটা Space দিয়ে লিখুন “Single” [ Enter ] এরপর b চাপুন ফলাফল : লিনাক্সের Single user Mood এ চলে আসছেন । এখন লিখুন passwd root [ Enter ] এখন নতুন পাসওয়ার্ড খানা টাইপ করেন [ এন্টার ] আবার টাইপ করেন [ এন্টার ] কাজ শেষ , এবার reboot টাইপ করেন । এখন নতুন পাসওয়ার্ড দিয়ে লগইন করেন। পুনশ্চ : যদি আপনার উইন্ডোজ এর সাথে ডুয়েল বুট করা থাকে তবে এই প্রক্রিয়া কাজ করবে না ।

Fix The BIOS in this system is not fully ACPI compliant in Windows 7

এই সমস্যা সমাধান করার জন্য আপনি নিচের ধাপ গুলো অনুসরণ করুন। ধাপ ১ :  আপানর  কম্পিউটার এ উইন্ডোজ এর ডিস্ক থেকে বুট করুন । নীচের মত উইন্ডো আসলে Shift + F10 চাপুন । এর ফলে কমান্ড প্রম্প্ট ওপেন হবে। ধাপ ২ : এখন CMD তে নিচের কমান্ড গুলি ধারবাহিক ভাবে লিখুন C: bootrec /FixMbr bootrec /FixBoot bootrec /RebuildBcd exit  এখানে  C হলো যে ড্রাইভ এ উইন্ডোজ দেয়া আছে।  আপনার যদি অন্য কোনো ড্রাইভ ( D, E, F, ..... ) এ উইন্ডোজ দেয়া থাকে তবে আপনাকে C এর জায়গায় সেই ড্রাইভ এর নাম লিখতে হবে।  উপরের সব কমান্ড যদি সঠিক ভাবে বিল্ড হয় তবে আপনি আপনার কম্পিউটার রিস্টার্ট দিন।  দেখবেন আপনার সমস্যা সমাধান হয়ে গেছে :D