Cod sursa(job #492972)

Utilizator klamathixMihai Calancea klamathix Data 16 octombrie 2010 16:43:03
Problema Radiatie Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.44 kb
#include<cstdio>
#include<vector>
#include<algorithm>
const int maxn = 15005;
const int maxm = 30010;
using namespace std;

int i , j , n , m , k , a , b, dad[maxn] , rang[maxn] , lev[maxn] , A[15][maxn] , B[15][maxn];
vector <int> G[maxn] , C[maxn];
bool seen[maxn];
struct edge { int x , y , cost;} e[maxm];
struct cmp { bool operator () ( const edge &X , const edge &Y ) { return (X.cost < Y.cost) ;}};

int find (int a) {
	int root, aux;
	for( root = a ; root!= dad[root] ; root = dad[root]);
	for ( ; a != dad[a]; ) {
		aux = dad[a];
		dad[a] = root;
		a = aux;
	}
	return root;
}

void join( int a , int b) {
	if ( rang[a] > rang[b] ) 
		dad[b] = a;
	else 
		dad[a] = b;
	if ( rang[a] == rang[b]) rang[b] ++;
}

void APM()
{
	int i , k = 0;
	sort( e + 1 , e + m + 1 , cmp() );
	for( i = 1 ; i <= n ; ++i ) dad[i] = i;
	for( i = 1 ; i <= m && k < n - 1 ; ++i )
			if ( find(e[i].x) != find(e[i].y)){
				join(find(e[i].x), find(e[i].y));
				G[e[i].x].push_back(e[i].y);
				C[e[i].x].push_back(e[i].cost);
				G[e[i].y].push_back(e[i].x);
				C[e[i].y].push_back(e[i].cost);
				++k;
			}
}

void DF(int node , int depth) {
	int i;
	seen[node] = 1 , lev[node] = depth;
	for( i = 0 ; i < G[node].size() ; ++i )
		if ( seen[G[node][i]] == 0){
		A[0][G[node][i]] = node ;
		B[0][G[node][i]] = C[node][i];
		DF(G[node][i] , depth + 1);
		}
}

int solve( int a , int b ) {
	int logA , logB , i , ans = -1;
	if ( lev[a] < lev[b] ) swap ( a, b );
	for( logA = 0 ; ( 1 << logA ) < a ; ++logA);
	for( logB = 0 ; ( 1 << logB ) < b ; ++logB);
	
	for( i = logA ; i >= 0 ; --i )
		if ( lev[a] - lev[b] >= ( 1 << i )){
			ans = max ( ans , B[i][a]);
			a = A[i][a];
	}
	
	for( i = logB ; i >= 0 ; --i )
		if ( A[i][a] && A[i][a] != A[i][b] ){
			ans = max ( ans , B[i][a] );
			ans = max ( ans , B[i][b]);
			a = A[i][a];
			b = A[i][a];
		}
return ans;
}

int main()
{
	freopen("radiatie.in","r",stdin);
	freopen("radiatie.out","w",stdout);
	
	scanf("%d %d %d",&n,&m,&k);
	for( i = 1 ; i <= m ; ++i ) 
		scanf("%d %d %d",&e[i].x,&e[i].y,&e[i].cost);
	APM();
	DF(1,0);
	
	for( j = 1 ; ( 1 << j ) < n ; ++j )
		for( i = 2 ; i <= n ; ++i ) 
			A[j][i] = A[j - 1][A[j - 1][i]];
	for( j = 1 ; ( 1 << j ) < n ; ++j )
		for( i = 2 ; i <= n ; ++i )
			B[j][i] = max( B[j - 1][i] , B[j - 1][A[j - 1][i]]);
	
	for( i = 1 ; i <= k ; ++i ) {
		scanf("%d %d",&a,&b);
		printf("%d\n",solve( a,b ));
	}
	
return 0;
}