Skip to main content

[ UVa ] 11749 - Poor Trade Advisor.

  • আমরা ইনপুট নেয়ার সময়ই max_ppa এর মান বের করবো ।
  • এখন ১ নং শহর থেকে যাত্রা শুরু করে n পর্যন্ত সব শহরেই যাব যদি না সেই শহর এ আমরা আগে কখনো গিয়ে থাকি। 
  • আমরা কোন একটা শহর থেকে যাত্রা শুরু করলে ওই শহর থেকে যতগুলি শহরে যাওয়া যায় তার সবগুলি তে যাওয়ার জন্য চেষ্টা করবো 
  • যদি একটা শহর u থেকে v তে যেতে PPA এর মান max_ppa এর সমান না হয় তবে আমরা সেই রাস্তাটা কে বাদ দিয়ে continue করবো । 
  • কোন এটা শহর থেকে যাত্রা শুরু করলে মোট কয়টা শহরে যাওয়া যায় সেটা number_of_city তে জমা করে রাখব । 
  • শেষে ম্যাক্সিমাম number_of_city ই হল আমাদের মহান সিজার সাহেবের Provience [ উপনিবেশ ] । যেটা খুজে বের করার জন্য তিনি অস্থির হয়ে গেছেন :P 
 কোড করার আগে :
  • আমাদের যদি একই road কয়েক বার ইনপুট দেয় এবং তাদের PPA যদি আলাদা আলাদা হয় যেমন : [ a, b ] = 10,  [ b, a ] = 20,  [ a, b ] = -111 তবে আমাদের কে ম্যাক্সিমাম PPA [ a, b ]=  20 কে নিতে হবে । 
  • PPA of that road [ fits in a signed 32 bit variable ] তার মানে PPA কিন্তু নেগেটিভ হতে পারে । তাই max_ppa এর মান শুরুতে -2147483648 দিতে হবে । শূন্য দিলে WA খেতে হবে ;)
কোড :
/**
* Problem : 11749 - Poor Trade Advisor.
* Verdict : Accepted.
* Writer : Mehadi Hasan Menon.
* Date : 26.12.16.
**/
#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#include <cstdio>
using namespace std;
const int mx = 505;
vector <int> network[mx];
int road_ppa[mx][mx];
bool visited[mx];
int max_ppa;
int dfs_count_node(int src_node)
{
stack <int> si;
int number_of_city = 1;
si.push(src_node);
visited[src_node] = true;
while(!si.empty())
{
int u = si.top();
si.pop();
for(int i = 0; i < network[u].size(); i++)
{
int v = network[u][i];
if( road_ppa[u][v] != max_ppa)
{
continue; // skip this road :)
}
if(visited[v] == false)
{
si.push(v);
visited[v] = true;
number_of_city += 1;
}
}
}
return number_of_city;
}
int main()
{
freopen("input.txt", "r+", stdin);
int n, m, x, y;
int ppa;
while(scanf("%d %d", &n, &m) && n != 0 && m != 0)
{
max_ppa = -2147483648;
for(int i = 1; i <= n; i++)
{
for(int j = 1; j <= n; j++)
{
road_ppa[i][j] = max_ppa;
}
}
for(int i = 0; i < m; i++)
{
scanf("%d %d %d", &x, &y, &ppa);
network[x].push_back(y);
network[y].push_back(x);
road_ppa[x][y] = road_ppa[y][x] = max(road_ppa[x][y], ppa);
max_ppa = max(max_ppa, ppa);
}
int max_number_of_city = 0;
for(int node = 1; node <= n; node++)
{
if(visited[node] == false)
{
int new_number_of_city = dfs_count_node(node);
max_number_of_city = max(max_number_of_city, new_number_of_city);
}
}
printf("%d\n", max_number_of_city);
for(int i = 1; i <= n; i++)
{
visited[i] = false;
network[i].clear();
}
}
return 0;
}
view raw 11749.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