[ UVa ] 11631 - Dark roads

• প্রথমে আমাদের কে বের করতে হবে Byteland এর রাস্তা গুলোর বর্তমান লাইটিং খরচ কত ।
• এরপর আমাদের কে Byteland এর রাস্তাগুলো  কিভাবে লাইটিং করলে সবচেয়ে কম খরচ হবে এবং সেই খরচ টা কত সেটা বের করতে হবে ।
• এটা বের করার জন্য আমরা Minimum Spanning Tree Algorithm ব্যাবহার করতে পারি । 
• শেষে আমরা আমাদের MST থেকে পাওয়া খরচ কে আমাদের মোট খরচ থেকে বাদ দিব তাহলেই আমাদের সমস্যার সমাধান হয়ে যাবে

কোড :

	/**
	* Problem : 11631 - Dark roads.
	* Verdict : Accepted.
	* Writer : Mehadi Hasan Menon.
	* Date : 28.12.16.
	**/
	#include <iostream>
	#include <vector>
	#include <algorithm>
	#include <queue>
	#include <cstdio>
	using namespace std;
	typedef pair <int, int> pii;
	typedef vector <int> vi;
	typedef vector <pii> vii;
	vector <vii> AdjList;
	vector <bool> taken;
	priority_queue <pii> pq;
	void process(int vtx)
	{
	taken[vtx] = true;
	for(int i = 0; i < AdjList[vtx].size(); i++)
	{
	pii v = AdjList[vtx][i];
	if(taken[v.first] == false)
	{
	// pair element default sort by 1st element
	// priority queue is max heap. this why use - sign
	// for getting min heap.
	pq.push(pii(-v.second, v.first));
	}
	}
	}
	int main()
	{
	freopen("input.txt", "r+", stdin);
	int m, n, x, y, z;
	while(scanf("%d %d", &m, &n) && m != 0 && n != 0)
	{
	// initialize our network with given size.
	AdjList.assign(m, vii());
	long long int total_cost = 0;
	for(int i = 0; i < n; i++)
	{
	scanf("%d %d %d", &x, &y, &z);
	AdjList[x].push_back( pii(y, z) );
	AdjList[y].push_back( pii(x, z) );
	total_cost += z;
	}
	taken.assign(m, false);
	long long int mst_cost = 0;
	// process our first city
	// we can choose any city.
	process(0);
	while(!pq.empty())
	{
	pii top = pq.top();
	pq.pop();
	if(taken[top.second] == false)
	{
	// get positive value of - value inserted into
	// our priority queue.
	mst_cost += -top.first;
	process(top.second);
	}
	}
	printf("%lld\n", total_cost - mst_cost);
	// clear our network after every steps :)
	for(int i = 0; i < m; i++) {
	AdjList[i].clear();
	}
	}
	return 0;
	}

view raw 11631.cpp hosted with ❤ by GitHub

হ্যাপি কোডিং :)