10034 - Freckles

Problem Link

এখানে N টা points দেওয়া থাকবে , প্রতিটা point কে একেকটা নোড ধরবো আর একটা থেকে আরেকটার distance হবে একটা edge এর weight। যদি (x₁,y₁) & (x₂,y₂) দুইটা point হয়, তাহলে-
                               distance between two points = √( (x₁ - x₂)² + (y₁-y₂)² )
বাকিটা কি করতে হবে এটা বুঝে যাওয়ার কথা ... না বুঝলেও সমস্যা নাই। এখন আমরা minimum weight পেতে MST ব্যবহার করব।

আরেকটা জিনিস খেয়াল রাখতে হবে, শেষ test case এর output print করার পর কোনো নতুন লাইন প্রিন্ট হবে না।

My Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<double, int>
const int MAX = 1005;
vector<pii> adj[MAX];
bool marked[MAX];

double Prim(int x)
{
    priority_queue<pii, vector<pii>, greater<pii> > Q;
    memset(marked, false, sizeof(marked));
    int y;
    double minimumcost = 0;
    pii p;
    Q.push(mp(0, x));

    while(!Q.empty())
    {
        p = Q.top();
        Q.pop();
        x = p.second;
        if(marked[x]==true)
            continue;
        minimumcost += p.first;
        marked[x] = true;
        for(int i = 0; i < adj[x].size(); i++)
        {
            y = adj[x][i].second;
            if(marked[y]==false)
                Q.push(adj[x][i]);
        }
    }
    return minimumcost;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        for(int i = 0; i < MAX; i++)
            adj[i].clear();
        int n;
        double minimumcost;
        double x[105], y[105];
        cin>>n;
        for(int i = 1; i <= n; i++)
            cin>>x[i]>>y[i];
        for(int i = 1; i <= n; i++)
        {
            for(int j = i+1; j <= n; j++)
            {
                double s;
                s = sqrt(pow(x[j]-x[i],2) + pow(y[j]-y[i],2));
                adj[i].push_back(mp(s,j));
                adj[j].push_back(mp(s,i));
            }
        }

        minimumcost = Prim(1);
        cout<<fixed<<setprecision(2)<<minimumcost<<endl;
        if(T)
            cout<<endl;
    }

    return 0;
}

10462 - Is There A Second Way Left?

Problem Link

একটা weighted undirected graph দেওয়া থাকবে। এখান থেকে আমাদের Second Best MST (Minimum spanning tree) বের করতে হবে। [এর আগে অবশ্যই Kruskal আর Prim এর উপর ভাল idea থাকা লাগবে, না থাকলে এই লিঙ্কটা দেখে আসব।]

তিন ধাপে আমরা এটা সমাধান করতে পারি।
১) graph connected কিনা check করব, যদি connected না হয় তাহলে "No way" প্রিন্ট করব। 
২) এখন MST বের করতে হবে এবং যে edge গুলো MST এর part ঐ গুলো চিহ্নিত করতে হবে।
৩) আগের edge গুলো (যা MST এর part ছিল) একটি একটি বাদ দিয়ে MST তৈরি করতে হবে আর এর minimum value টা নিতে হবে। এইভাবেই আমরা Second Best MST পাব।

My Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pii pair<int, int>
const int MAX = 300;
int id[MAX], nodes, edges, cnt = 0;
pair<ll, pii> p[MAX];
vector<int>edge;

void initialize()
{
    for(int i = 0; i < MAX; i++)
        id[i] = i;
}

int root(int x)
{
    if(id[x] == x)
        return x;
    return id[x] = root(id[x]);
}

void make_union(int x, int y)
{
    id[root(x)] = id[root(y)];
}

ll Kruskal()
{
    initialize();
    cnt = 0;
    int x, y, flag = 0;
    ll cost, minimumcost = 0;
    for(int i = 0; i < edges; i++)
    {
        x = p[i].second.first;
        y = p[i].second.second;
        cost = p[i].first;

        if(root(x)!=root(y))
        {
            flag++;
            cnt++;
            edge.push_back(i);
            minimumcost += cost;
            make_union(x,y);
        }
    }
    if(flag==nodes-1)
        return minimumcost;
    return -1;
}

ll SBMST()  ///function to find second best MST
{
    ll maximum = 1e18;

    for(int j = 0; j < cnt; j++)
    {
        initialize();
        int x, y, flag = 0;
        ll cost, minimumcost = 0;
        for(int i = 0; i < edges; i++)
        {
            if(edge[j]!=i)  ///age use hoise emn value baad dibo
            {
                x = p[i].second.first;
                y = p[i].second.second;
                cost = p[i].first;

                if(root(x)!=root(y))
                {
                    flag++;
                    minimumcost += cost;
                    make_union(x,y);
                }
            }
        }
        //cout<<minimumcost<<endl;
        if(flag==nodes-1)
            maximum = min(minimumcost,maximum);  ///minimum value ta nibo
    }

    if(maximum!=1e18)
        return maximum;
    return -1;
}

int main()
{
    int T;
    cin>>T;
    for(int t = 1; t <= T; t++)
    {
        int u, v;
        ll weight;
        cin>>nodes>>edges;
        for(int i = 0; i < edges; i++)
        {
            cin>>u>>v>>weight;
            p[i] = mp(weight, mp(u,v));
        }

        sort(p, p + edges);

        cout<<"Case #"<<t<<" : ";
        if(Kruskal()==-1)
            cout<<"No way"<<endl;
        else
        {
            ll minimumcost = SBMST();

            if(minimumcost==-1)
                cout<<"No second way"<<endl;
            else
                cout<<minimumcost<<endl;
        }

        for(int i = 0; i < MAX; i++)  /// Reset the pair (er chaite valo way jana nai -_-)
        {
            p[i].first = 0;
            p[i].second.first = 0;
            p[i].second.first = 0;
        }
        edge.clear();
    }

    return 0;
}