Skip to main content

[ UVa ] 10462 - Is There A Second Way Left ?

  • এই সমস্যা টি 2nd best MST বের করা সম্পর্কিত সমস্যা । 
  • এই সমস্যা সমাধান করার জন্য প্রথমে MST বের করতে হবে । MST বের করার পর আমরা চেক করবো সবগুলি নোড একই সেটে আছে কি না ? যদি না থাকে তবে No way প্রিন্ট করতে হবে । 
  • আর যদি সবগুলি একই সেটে থাকে তবে দেখব মোট নোড সংখ্যা ইনপুট দেয়া এজের থেকে ১ বেশি কি না? যদি কেবল মাত্র ১ বেশি হয় তবে 2nd best MST খুজে দেখার দরকার নাই । কারণ 2nd best MST পাওয়া যাবে না। এবং আমদের কে No second way প্রিন্ট করেতে হবে ।
  • যদি নোড থেকে এজের পার্থক্য ১ না হয় তবে আমাদের কে 2nd best MST খুজে বের করতে হবে । এবং আমাদের কে সেটাই প্রিন্ট করেতে হবে । 
  • এখন দেখা গেলও যে MST এবং 2nd best MST এর খরচ একই সেই ক্ষেত্রে আমদের কে প্রথমে পাওয়া MST খরচকেই প্রিন্ট করতে হবে । এই ক্ষেত্রে No second way প্রিন্ট করলে WA খেতে হবে । 
কোড :
/**
* Problem : 10462 - Is There A Second Way Left?
* Verdict : Accepted.
* Time : 0.010 ms.
* Writer : Mehadi Hasan Menon.
****/
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
struct edge {
int u, v, w;
bool taken;
bool operator < (const edge &p) const {
return w < p.w;
}
};
const int mx = 105;
const int inf = INT_MAX;
int boss[mx];
vector <edge> edge_list;
void init_boss(int n) {
for(int i = 1; i <= n; i++) {
boss[i] = i;
}
}
int find_boss(int x) {
return (boss[x] == x) ? x : boss[x] = find_boss(boss[x]);
}
bool is_same_set(int x, int y) {
return (find_boss(x) == find_boss(y)) ? true : false;
}
int get_1st_mst(int n)
{
int min_cost, sz;
init_boss(n);
sort(edge_list.begin(), edge_list.end());
sz = edge_list.size();
min_cost = 0;
for(int i = 0; i < sz; i++)
{
int u = find_boss(edge_list[i].u);
int v = find_boss(edge_list[i].v);
if(u != v) {
boss[v] = u;
min_cost += edge_list[i].w;
edge_list[i].taken = true;
}
}
return min_cost;
}
int get_2nd_mst(int n)
{
int sz, min_cost;
sz = edge_list.size();
min_cost = inf;
for(int i = 0; i < sz; i++)
{
if(edge_list[i].taken == true)
{
int tmp_cost = 0, tmp = edge_list[i].w;
edge_list[i].w = inf;
init_boss(n);
for(int j = 0; j < sz; j++)
{
int u = find_boss(edge_list[j].u), v = find_boss(edge_list[j].v);
if(u != v && edge_list[j].w != inf) {
boss[v] = u;
tmp_cost += edge_list[j].w;
}
}
edge_list[i].w = tmp;
// check is it possible to create MST or not
for(int i = 2; i <= n; i++) {
if(is_same_set(i, 1) == false) {
tmp_cost = inf;
break;
}
}
min_cost = min(min_cost, tmp_cost);
}
}
return min_cost;
}
int main()
{
freopen("input.txt", "r+", stdin);
int tc, v, e, start, end, cost;
scanf("%d", &tc);
for(int t = 1; t <= tc; t++)
{
scanf("%d %d", &v, &e);
for(int i = 0; i < e; i++)
{
scanf("%d %d %d", &start, &end, &cost);
edge e;
e.u = start, e.v = end, e.w = cost, e.taken = false;
edge_list.push_back(e);
}
int cost1 = get_1st_mst(v);
bool flag = false;
for(int i = 2; i <= v; i++) {
if(is_same_set(i, 1) == false) {
flag = true;
break;
}
}
printf("Case #%d : ", t);
if(flag) {
printf("No way\n");
}
else {
if(v == e + 1) {
printf("No second way\n");
}
else {
// if cost1 == cost2 then it's treated as 2nd Way :)
int cost2 = get_2nd_mst(v);
printf("%d\n", cost2);
}
}
edge_list.clear();
}
return 0;
}
view raw 10462.cpp hosted with ❤ by GitHub

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