「NOIP 2013 D1T3」貨車運輸

傳送門

problem

A 國有 n n n 座城市，編号從 1 1 1 到 n n n，城市之間有 m m m 條雙向道路。每一條道路對車輛都有重量限制，簡稱限重。現在有 q q q 輛貨車在運輸貨物，司機們想知道每輛車在不超過車輛限重的情況下，最多能運多重的貨物。

資料範圍： 0 < n < 1 0 4 0<n<10^4 0<n<104， 0 < m < 5 × 1 0 4 0<m<5\times 10^4 0<m<5×104， 0 < q < 3 × 1 0 4 0<q<3\times 10^4 0<q<3×104。

solution

重新寫了一遍，當做是複習了吧。

做一遍最大生成樹，把 Kruskal 重構樹建出來，那麼兩點的答案就是 lca 的權值。

時間複雜度 O ( n log ⁡ n ) O(n\log n) O(nlogn)。

code

#include<bits/stdc++.h>
using namespace std;
namespace IO{
	const int Rlen=1<<22|1;
	char buf[Rlen],*p1,*p2;
	inline char gc(){
		return (p1==p2)&&(p2=(p1=buf)+fread(buf,1,Rlen,stdin),p1==p2)?EOF:*p1++;
	}
	template<typename T>
	inline T Read(){
		char c=gc();T x=0,f=1;
		while(!isdigit(c))  f^=(c=='-'),c=gc();
		while( isdigit(c))  x=(x+(x<<2)<<1)+(c^48),c=gc();
		return f?x:-x;
	}
	inline int in()  {return Read<int>();}
}
using IO::in;
const int N=2e4+5,M=5e4+5;
int n,m,q,tot;
struct edges{int u,v,w;}e[M];
bool operator<(const edges &p,const edges &q)  {return p.w>q.w;}
int father[N],son[N][2],dep[N],val[N],fa[N][15];
int find(int x)  {return (father[x]==x)?x:father[x]=find(father[x]);}
void Kruskal(){
	sort(e+1,e+m+1),tot=n;
	for(int i=1;i<=n;++i)  father[i]=i;
	for(int i=1;i<=m;++i){
		int u=find(e[i].u),v=find(e[i].v);
		if(u!=v){
			son[++tot][0]=u,son[tot][1]=v;
			fa[u][0]=fa[v][0]=father[u]=father[v]=father[tot]=tot;
			val[tot]=e[i].w;
		}
	}
}
void dfs(int x){
	for(int i=1;i<=14;++i)  fa[x][i]=fa[fa[x][i-1]][i-1];
	if(son[x][0])  dep[son[x][0]]=dep[x]+1,dfs(son[x][0]);
	if(son[x][1])  dep[son[x][1]]=dep[x]+1,dfs(son[x][1]);
}
int LCA(int x,int y){
	if(dep[x]<dep[y])  swap(x,y);
	for(int i=14;~i;--i)  if(dep[fa[x][i]]>=dep[y])  x=fa[x][i];
	if(x==y)  return x;
	for(int i=14;~i;--i)  if(fa[x][i]!=fa[y][i])  x=fa[x][i],y=fa[y][i];
	return fa[x][0];
}
int main(){
	n=in(),m=in();
	for(int i=1;i<=m;++i)  e[i].u=in(),e[i].v=in(),e[i].w=in();
	Kruskal();
	for(int i=tot;i>=1;--i)  if(!dep[i])  dep[i]=1,dfs(i);
	q=in();
	while(q--){
		int x=in(),y=in(),lca=LCA(x,y);
		printf("%d\n",val[lca]?val[lca]:-1);
	}
	return 0;
}