[ 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