Cod sursa(job #7827)

Utilizator bogdan2412Bogdan-Cristian Tataroiu bogdan2412 Data 22 ianuarie 2007 18:59:01
Problema Radiatie Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.64 kb
#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

#define FOR(i,a,b) for( int i = (a); i < (b); ++i )
#define FORI(it,v) for( it = (v).begin(); it != (v).end(); ++it )
#define ALL(v) (v).begin(), (v).end()

#define MAXN 16384

struct graphEdge { int x, y, cst; };

int N, NR_M, K;
vector< graphEdge > edges;

int p[MAXN];
vector< pair<int, int> > con[MAXN];
int T[15][MAXN], M[15][MAXN], alt[MAXN];

int log[MAXN];

inline graphEdge make_graphEdge( int x, int y, int cst )
{
	graphEdge tmp;
	tmp.x = x;
	tmp.y = y;
	tmp.cst = cst;
	return tmp;
}

int cmp(graphEdge a, graphEdge b)
{
	return a.cst < b.cst;
}

void dfs(int k, int l)
{
	vector< pair<int, int> > :: iterator it;
	FORI(it, con[k])
	{
		if ((*it).first == l) continue;
		T[0][ (*it).first ] = k;
		M[0][ (*it).first ] = (*it).second;
		alt[ (*it).first ] = alt[k] + 1;
		dfs( (*it).first, k );
	}
}

int getset(int x)
{
	if (x == p[x])
		return x;
	return p[x] = getset( p[x] );
}

int main()
{
	freopen("radiatie.in", "rt", stdin);
	freopen("radiatie.out", "wt", stdout);
	scanf("%d %d %d", &N, &NR_M, &K);
	for (; NR_M; NR_M--)
	{
		int x, y, cst;
		scanf("%d %d %d", &x, &y, &cst);
		edges.push_back( make_graphEdge( x, y, cst ) );
	}

	FOR(i, 0, N + 1)
		p[i] = i;
	sort(ALL(edges), cmp);

	vector< graphEdge > :: iterator it;
	FORI(it, edges)
	{
		int X, Y, CST;
		X = (*it).x;
		Y = (*it).y;
		CST = (*it).cst;

		if (getset(X) == getset(Y)) continue;

		con[X].push_back( make_pair( Y, CST ) );
		con[Y].push_back( make_pair( X, CST ) );
		X = getset(X);
		Y = getset(Y);
		if (rand() % 2)
			p[X] = Y;
		else
			p[Y] = X;
	}

	dfs( 1, 0 );

	for (int i = 2, j = 0; i <= N; i++)
	{
		if ((1 << (j + 1)) == i)
			j++;
		log[i] = j;
	}

	for (int i = 1; (1 << i) <= N; i++)
		for (int j = 1; j <= N; j++)
		{
			T[i][j] = T[i - 1][ T[i - 1][j] ];
			M[i][j] = max( M[i - 1][j], M[i - 1][ T[i - 1][j] ] );
		}

	for (; K; K--)
	{
		int x, y, MAX = 0;
		scanf("%d %d", &x, &y);

		for (; alt[x] > alt[y]; )
		{
			int lg = log[ alt[x] - alt[y] ];
			MAX = max( MAX, M[lg][x] );
			x = T[lg][x];
		}
		for (; alt[x] < alt[y]; )
		{
			int lg = log[ alt[y] - alt[x] ];
			MAX = max( MAX, M[lg][y] );
			y = T[lg][y];
		}

		for (int step = log[ alt[x] ]; step; step--)
			if (T[step][x] != T[step][y])
			{
				MAX = max( MAX, M[step][x] );
				MAX = max( MAX, M[step][y] );
				x = T[step][x];
				y = T[step][y];
			}

		if (x != y)			//LCA = T[0][x];
		{
			MAX = max( MAX, M[0][x] );
			MAX = max( MAX, M[0][y] );
		}
		printf("%d\n", MAX);
	}
	return 0;
}