Skip to main content

[ UVa ] 10842 - Traffic Flow

  • আমরা MST তে যে কাজটা করি এই সমস্যাতে তার উল্টা কাজটা করতে হবে । অর্থাৎ আমাদের কে Maximum Spanning Tree বানাতে হবে । 
  • যে যে এজ নিয়ে আমাদের Maximum Spanning Tree গঠিত হবে । সেই এজ গুলির মধ্যে যে এজের ওয়েট সবচেয়ে কম সেই ওয়েট কে প্রিন্ট করতে হবে । 
  • এই সমস্যা তে আমাদের কে কিছু কর্নার কেইস বিবেচনা করতে হবে । যেমন : আমাদের ইনপুটে যদি  m = 0 হয় তবে max_cost কত হবে ? max_cost হবে int এর ম্যাক্সিমাম ভেলু অর্থাৎ INT_MAX = 2147483647 
  • যদি একই এজ একের অধিক বার ইনপুটে দেয়া থাকে তবে তাদের মধ্যে যেটার ওয়েট ম্যাক্সিমাম সেই এজেটি নিয়ে বাকি গুলো বাদ দিতে হবে ।  [ প্রথম ইনপুট লক্ষণীয় ]
  • যদি একই নোড থেকে একই নোডে আসার কোন পাথ থাকে অর্থাৎ যদি u == v হয়ে তবে আমাদের কে সেই এজটি গ্রাফ থেকে প্রথমেই বাদ দিতে হবে :)  
কোড :
/**
* 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;
}
view raw 10842.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