TIOJ 1163 6.施工中的道路

poao899    1168K    155MS    G++    1.46K     2009-11-12 09:26:18                                        .


這題太帥了XD













MST + [                 ]...











唔反正就是很神奇的東西

//**************************

//1163

#include<stdio.h>
#include<algorithm>
#define MAXE 50002
#define MAXV 30002
struct edge{
	int i,j,cost;
	bool operator<(const edge &b)const{
		return cost<b.cost;
	}
}E[MAXE];
int rank[MAXV],root[MAXV],tmp[MAXV];
int v,e,q,st,ed,edgeUsed;
int visit[MAXV],toFaLen[MAXV];
int find(int a){
	return a==root[a]?a:find(root[a]);
}
void unionByRank(int a,int b,int ra,int rb,int cost){
	//Let rank[ra]<=rank[rb]
	if(rank[ra]>rank[rb]){
		unionByRank(b,a,rb,ra,cost);return;
	}
	toFaLen[ra]=cost>?toFaLen[b];
	root[ra]=rb;
	if(rank[ra]==rank[rb])
		rank[rb]++;
}
main(){
	//Initialize
	for(int i=0;i<MAXV;i++){
		rank[i]=1;
		root[i]=i;
	}
	scanf("%d%d",&v,&e);
	for(int i=0;i<e;i++)
		scanf("%d%d%d",&E[i].i,&E[i].j,&E[i].cost);
	//MST
	std::sort(E,E+e);
	for(int i=0;i<e&&edgeUsed<v-1;i++){
		int a=E[i].i,b=E[i].j,ra=find(a),rb=find(b);
		if(ra!=rb){
			//printf("add %d %d:%d\n",E[i].i,E[i].j,E[i].cost);
			edgeUsed++;
			unionByRank(a,b,ra,rb,E[i].cost);
		}
	}
	//Query
	scanf("%d",&q);
	for(int i=1;i<=q;i++){
		scanf("%d%d",&st,&ed);
		int max=0,j;
		bool reach=0;
		visit[st]=i;
		for(j=st;root[j]!=j;j=root[j]){
			visit[j]=i;
			tmp[j]=max;
			if(max<toFaLen[j])max=toFaLen[j];
		}
		visit[j]=i;
		tmp[j]=max;
		max=0;
		for(j=ed;root[j]!=j;j=root[j]){
			if(visit[j]==i){reach=1;break;}
			if(max<toFaLen[j])max=toFaLen[j];
		}
		reach=reach||(visit[j]==i);
		reach?printf("%d\n",max>?tmp[j]):puts("-1");
	}
}