Cod sursa(job #476046)

Utilizator andrei.dAndrei Diaconeasa andrei.d Data 9 august 2010 16:44:55
Problema Radiatie Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.58 kb
#include <cstdio>
#include <algorithm>

using namespace std;

#define file_in "radiatie.in"
#define file_out "radiatie.out"

#define nmax 32397

int a[nmax];
int b[nmax];
int c[nmax];
int n,m,k;
int tata[nmax];
int ind[nmax];
int viz[nmax];
int cost[nmax];

int cmp(int i, int j)
{
	return c[i]<c[j];
}


void citire()
{
	int i;
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d %d", &n, &m, &k);
	for (i=1;i<=m;++i)
	{
		scanf("%d %d %d", &a[i], &b[i], &c[i]);
		ind[i]=i;
	}
	for (i=1;i<=n;++i) tata[i]=i;
	sort(ind+1,ind+m+1,cmp);
}



int father(int x)
{
	if(x==tata[x])
		return x;
	return father(tata[x]);
}

void unite(int i, int j)
{
	tata[i]=j;
}

void dfs(int nod)
{
	if (tata[nod]==nod)
	{
		viz[nod]=1;
		return ;
	}
	dfs(tata[nod]);
	viz[nod]=viz[tata[nod]]+1;
}


int query(int x, int y)
{
	int c=0;
	if (viz[x]<viz[y])
		swap(x,y);

	while(viz[x]>viz[y])
	{
		c=max(c,cost[x]);
		x=tata[x];
	}
	while(x!=y)
	{
		c=max(c,cost[x]);
		c=max(c,cost[y]);
		x=tata[x];
		y=tata[y];
	}
	
	return c;
}



void solve()
{
	int i,t1,t2,x,y;
	for(i=1;i<=m;i++)
	{
		t1=father(a[ind[i]]);
		t2=father(b[ind[i]]);
		if(t1!=t2)
		{
			unite(t1,t2);
			cost[t1]=c[ind[i]];
		}
	}

	//for (i=1;i<=n;++i) printf("%d ", cost[i]);
	//printf("\n");
	for (i=1;i<=n;++i)
	      if (!viz[i])
			 dfs(i);

	while(k--)
	{
		scanf("%d %d", &x,&y);
		printf("%d\n", query(x,y));
	}
}
	
int main()
{
	citire();
	solve();
	
	fclose(stdin);
	fclose(stdout);
	
	return 0;
	
}