- এই সমস্যা টি 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 খেতে হবে ।
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 : 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; | |
} |
Comments
Post a Comment