মডিউল ১৪_৩ঃ Minimum Cost for Business

আপনি এমন একটি শহরে বাস করেন যেখানে N বিল্ডিং রয়েছে এবং E রাস্তাগুলি সেই বিল্ডিংগুলিকে সংযুক্ত করে৷ প্রতিটি রাস্তার একটি দূরত্ব রয়েছে এবং সেগুলি দ্বিমুখী রাস্তা। আপনি আপনার শহরে একটি ব্যবসা শুরু করতে চান যেখানে আপনি ISP পরিষেবা প্রদান করবেন। সেই কারণে, আপনাকে রাস্তার মাধ্যমে আপনার কেন্দ্রীয় তারের সাথে সমস্ত বিল্ডিং সংযোগ করতে হবে। অপটিক্যাল ফাইবারের দাম বেশি হওয়ায় যতটা সম্ভব খরচ কমাতে চান। আপনি যদি রাস্তার দূরত্ব জানেন তবে আপনি কি আপনার তারের সাথে সমস্ত বিল্ডিং সংযোগ করার জন্য সর্বনিম্ন খরচ গণনা করতে পারেন? অপটিক্যাল ফাইবারের খরচ যেকোনো রাস্তার দূরত্বের সমান।

সমাধানঃ

এই প্রব্লেমে আপনাকে মিনিমাম খরচে সংযোগটি করতে হবে। যখন আপনার থেকে এমনভাবে cost বের করতে হবে যেইখানে নোডগুলোর মধ্যে কোন multiple connection রাখা যাবে নাহ, তখনি আমরা MST(Minimum Spanning Tree) ব্যবহার করে প্রব্লেমটি সমাধান করতে পারি, কারন MST একটি tree আর আমরা জানি tree তে multiple edge থাকে নাহ।

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int parent[N];
int group_size[N];
void dsu_initialize(int n)
{
    for (int i = 0; i < n; i++)
    {
        parent[i] = -1;
        group_size[i] = 1;
    }
}
int dsu_find(int node)
{
    if (parent[node] == -1)
        return node;
    int leader = dsu_find(parent[node]);
    parent[node] = leader;
    return leader;
}
void dsu_union_by_size(int node1, int node2)
{
    int leaderA = dsu_find(node1);
    int leaderB = dsu_find(node2);
    if (group_size[leaderA] > group_size[leaderB])
    {
        parent[leaderB] = leaderA;
        group_size[leaderA] += group_size[leaderB];
    }
    else
    {
        parent[leaderA] = leaderB;
        group_size[leaderB] += group_size[leaderA];
    }
}
class Edge
{
public:
    int u, v, w;
    Edge(int u, int v, int w)
    {
        this->u = u;
        this->v = v;
        this->w = w;
    }
};
bool cmp(Edge a, Edge b)
{
    return a.w < b.w;
}
int main()
{
    int n, e;
    cin >> n >> e;
    dsu_initialize(n);
    vector<Edge> edgeList;
    while (e--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        edgeList.push_back(Edge(u, v, w));
    }
    sort(edgeList.begin(), edgeList.end(), cmp);
    int totalCost = 0;
    for (Edge ed : edgeList)
    {
        int leaderU = dsu_find(ed.u);
        int leaderV = dsu_find(ed.v);
        if (leaderU == leaderV)
        {
            continue;
        }
        else
        {
            dsu_union_by_size(ed.u, ed.v);
            totalCost += ed.w;
        }
    }
    cout << totalCost << endl;
    return 0;
}