Cod sursa(job #475593)

Utilizator freak93Adrian Budau freak93 Data 7 august 2010 17:00:50
Problema Radiatie Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.29 kb
#include<fstream>
#include<algorithm>

using namespace std;

const char iname[]="radiatie.in";
const char oname[]="radiatie.out";
const int maxn=15007;

ifstream f(iname);
ofstream g(oname);

struct muchie
{
    int a,b,c;
}a[maxn*2];

int height[maxn],A[maxn],cost[maxn],n,m,k,i;
bool operator<(const muchie& a,const muchie& b)
{
    return a.c<b.c;
}

int anc(int x)
{
    int y;
    for(y=x;A[y]!=y;y=A[y]);
    return y;
}

void get_height(int x)
{
    if(A[x]==x)
    {
        height[x]=1;
        return;
    }
    if(height[A[x]]==0)
        get_height(A[x]);
    height[x]=height[A[x]]+1;
}

int query(int x,int y)
{
    int rez=0;
    while(height[x]>height[y])
        rez=max(rez,cost[x]),x=A[x];
    while(height[y]>height[x])
        rez=max(rez,cost[y]),y=A[y];
    while(x!=y)
        rez=max(rez,cost[x]),rez=max(rez,cost[y]),x=A[x],y=A[y];
    return rez;
}

int main()
{
    f>>n>>m>>k;
    for(i=1;i<=m;++i)
        f>>a[i].a>>a[i].b>>a[i].c;
    sort(a+1,a+m+1);
    for(i=1;i<=n;++i)
        A[i]=i;
    for(i=1;i<=m;++i)
    {
        int x=anc(a[i].a),y=anc(a[i].b);
        if(x!=y)
            A[x]=y,cost[x]=a[i].c;
    }
    for(i=1;i<=n;++i)
        if(!height[i])
            get_height(i);
    for(i=1;i<=k;++i)
    {
        int x,y;
        f>>x>>y;
        g<<query(x,y)<<"\n";
    }
}