- আমরা MST তে যে কাজটা করি এই সমস্যাতে তার উল্টা কাজটা করতে হবে । অর্থাৎ আমাদের কে Maximum Spanning Tree বানাতে হবে ।
- যে যে এজ নিয়ে আমাদের Maximum Spanning Tree গঠিত হবে । সেই এজ গুলির মধ্যে যে এজের ওয়েট সবচেয়ে কম সেই ওয়েট কে প্রিন্ট করতে হবে ।
- এই সমস্যা তে আমাদের কে কিছু কর্নার কেইস বিবেচনা করতে হবে । যেমন : আমাদের ইনপুটে যদি m = 0 হয় তবে max_cost কত হবে ? max_cost হবে int এর ম্যাক্সিমাম ভেলু অর্থাৎ INT_MAX = 2147483647
- যদি একই এজ একের অধিক বার ইনপুটে দেয়া থাকে তবে তাদের মধ্যে যেটার ওয়েট ম্যাক্সিমাম সেই এজেটি নিয়ে বাকি গুলো বাদ দিতে হবে । [ প্রথম ইনপুট লক্ষণীয় ]
- যদি একই নোড থেকে একই নোডে আসার কোন পাথ থাকে অর্থাৎ যদি u == v হয়ে তবে আমাদের কে সেই এজটি গ্রাফ থেকে প্রথমেই বাদ দিতে হবে :)
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 : 10842 - Traffic Flow. | |
* Verdict : Accepted. | |
* Time : 0.060 ms. | |
* Writer : Mehadi Hasan Menon. | |
**/ | |
#include <iostream> | |
#include <algorithm> | |
#include <vector> | |
#include <climits> // for INT_MAX | |
using namespace std; | |
const int mx = 105; | |
int graph[mx][mx]; | |
int root[mx]; | |
struct edge { | |
int u, v, w; | |
bool operator < (const edge &p) const { | |
return w > p.w; | |
} | |
}; | |
void init(int n) { | |
for(int i = 0; i < n; i++) { | |
root[i] = i; | |
} | |
} | |
int find_root(int x) { | |
return (root[x] == x) ? x : root[x] = find_root(root[x]); | |
} | |
int main() | |
{ | |
freopen("input.txt", "r+", stdin); | |
int tc, n, m, x, y, c; | |
scanf("%d", &tc); | |
for(int t = 1; t <= tc; t++) | |
{ | |
scanf("%d %d", &n, &m); | |
for(int i = 0; i < n; i++) | |
{ | |
for(int j = 0; j < n; j++) | |
{ | |
graph[i][j] = 0; | |
} | |
} | |
for(int i = 0; i < m; i++) | |
{ | |
scanf("%d %d %d", &x, &y, &c); | |
if(graph[x][y] != 0) { | |
graph[x][y] = max(graph[x][y], c); | |
} | |
else { | |
graph[x][y] = c; | |
} | |
} | |
vector <edge> edge_list; | |
for(int i = 0; i < n; i++) | |
{ | |
for(int j = 0; j < n; j++) | |
{ | |
if(i != j && graph[i][j] != 0) { | |
edge e; | |
e.u = i, e.v = j, e.w = graph[i][j]; | |
edge_list.push_back(e); | |
} | |
} | |
} | |
sort(edge_list.begin(), edge_list.end()); | |
int sz, min_cost; | |
sz = edge_list.size(); | |
min_cost = INT_MAX; | |
init(n); | |
for(int i = 0; i < sz; i++) | |
{ | |
int u = find_root(edge_list[i].u); | |
int v = find_root(edge_list[i].v); | |
if(u != v) { | |
root[v] = u; | |
min_cost = min(min_cost, edge_list[i].w); | |
} | |
} | |
printf("Case #%d: %d\n", t, min_cost); | |
} | |
return 0; | |
} |
Comments
Post a Comment