Cod sursa(job #2652378)

Utilizator NeacsuMihaiNeacsu Mihai NeacsuMihai Data 24 septembrie 2020 19:48:08
Problema Radiatie Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.39 kb
#include <iostream>
#include <fstream>
#include <algorithm>

using namespace std;

ifstream fin ("radiatie.in");
ofstream fout ("radiatie.out");

short f[15001];
int max1[15001], ct[15001], tt[15001], rg[15001], sterg[15001];

struct laturi
{
    int a, b, c;
}v[30001];

int comparare(laturi x, laturi y)
{
    return x.c<y.c;
}

int find (int x)
{
    while(tt[x]!=x)
    {
        x=tt[x];
    }
    return x;
}

void unite (int a, int b, int x, int y, int c)
{
    if(rg[x]>rg[y])
    {
        ct[b]=c;
        tt[b]=a;
    }

    else
    {
        ct[a]=c;
        tt[a]=b;
    }

    if(rg[x]==rg[y]) rg[y]++;
}

int main()
{
    int n, m, k, i, y, nr, a, b, numar_sterg;
    fin>>n>>m>>k;

    for(i=1; i<=m; i++)
    {
        fin>>v[i].a>>v[i].b>>v[i].c;
    }

    sort(v+1, v+m+1, comparare);

    for(i=1; i<=n; i++)
    {
        rg[i]=1;
        tt[i]=i;
    }

    nr=0;
    i=1;
    while(nr<n-1)
    {
        int aux1=find(v[i].a);
        int aux2=find(v[i].b);


        if(aux1!=aux2)
        {
            nr++;
            unite(v[i].a, v[i].b, aux1, aux2, v[i].c);
        }

        i++;
    }

    for(y=1; y<=k; y++)
    {
        fin>>a>>b;

        if(a==b) fout<<0<<"\n";

        else
        {
            numar_sterg=0;
            f[a]=1;
            f[b]=2;
            sterg[++numar_sterg]=a;
            sterg[++numar_sterg]=b;

            while(tt[a]!=tt[b] && f[ tt[a] ]!=2 && f[ tt[b] ]!=1)
            {
                f[ tt[a] ]=1;
                f[ tt[b] ]=2;

                sterg[++numar_sterg]=tt[a];
                sterg[++numar_sterg]=tt[b];

                max1[ tt[a] ]=max(max1[a], ct[a]);
                max1[ tt[b] ]=max(max1[b], ct[b]);

                a=tt[a];
                b=tt[b];
            }

            if(f[ tt[b] ]==1)
            {
                fout<<max( max1[ tt[b] ], max( max1[ b ], ct[b]))<<"\n";
            }

            else if(f[ tt[a] ]==2)
            {
                fout<<max( max1[ tt[a] ], max( max1[ a ], ct[a]))<<"\n";
            }

            else
            {
                fout<<max(max1[a], max(max1[b], max(ct[a], ct[b])))<<"\n";
            }

            for(i=1; i<=numar_sterg; i++)
            {
                max1[ sterg[i] ]=0;
                f[ sterg[i] ]=0;
            }
        }
    }
}