【NOIP2013】貨車運輸

Description

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

Input

第一行有兩個用一個空格隔開的整數 n，m，表示 A 國有 n 座城市和 m 條道路。?
接下來 m 行每行 3 個整數 x、y、z，每兩個整數之間用一個空格隔開，表示從 x 號城市到 y 號城市有一條限重為 z 的道路。注意：x 不等于 y，兩座城市之間可能有多條道路。?
接下來一行有一個整數 q，表示有 q 輛貨車需要運貨。?
接下來 q 行，每行兩個整數 x、y，之間用一個空格隔開，表示一輛貨車需要從 x 城市運輸貨物到 y 城市，注意：x 不等于 y。

Output

輸出共有 q 行，每行一個整數，表示對于每一輛貨車，它的最大載重是多少。如果貨車不能到達目的地，輸出-1。

Sample Input

4 3?
1 2 4?
2 3 3?
3 1 1?
3?
1 3?
1 4?
1 3

Sample Output

3?
-1?
3

Hint

對于 30%的數據，0 ＜ n ＜1,000，0 ＜ m ＜ 10,000，0 ＜ q ＜ 1,000；

對于 100%的數據，0 ＜ n ＜ 10,000，0 ＜ m ＜ 50,000，0 ＜ q ＜ 30,000，0 ≤ z ≤ 100,000。

題解：

這個題目是找每條路徑上的最大邊權的最小最大值，首先要知道結論，圖中任意兩點路徑的最大最小值一定是在這個圖的最大生成樹上，因為我們做克魯斯卡爾的時候，是將邊從大到到小排序，然后一顆生成樹包含了圖中任意節點并且因為是從大到小，所以所以的邊都盡量選最大的，那么限制條件——那個最小值一定在樹上，所以把樹扣出來，用倍增或者是樹鏈剖分維護一下就可以了。主要對森林的處理，用并查集維護同時向一個聯通塊連一條-1的邊。

代碼：

#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<cstring>
const int MAXN=200300;
using namespace std;
int n,m,q,num=0,faa[MAXN];
struct edge1{int from,to,quan;void read(){scanf("%d%d%d",&from,&to,&quan);}
}e[MAXN*2];
struct edge3{int from,to,quan;
}h[MAXN*2];
struct edge{int to,quan,first,next;
}a[MAXN*2];
int son[MAXN],size[MAXN],deep[MAXN],fa[MAXN];
int top[MAXN],id[MAXN],w[MAXN],numm;
struct tree{int l,r,minn;
}tr[MAXN*4];void cl(){for(int i=1;i<=MAXN*4-1;i++) tr[i].minn=1<<30;memset(fa,0,sizeof(fa));memset(son,0,sizeof(son));memset(size,0,sizeof(size));memset(deep,0,sizeof(deep));memset(top,0,sizeof(top));memset(id,0,sizeof(id));memset(w,0,sizeof(w));
}bool comp(edge1 x,edge1 y){if(x.quan>y.quan) return 1;return 0;
}void addedge(int from,int to,int quan){a[++num].to=to;a[num].quan=quan;a[num].next=a[from].first;a[from].first=num;
}int find(int now){if(now!=faa[now]) faa[now]=find(faa[now]);return faa[now];
}void hebin(int x,int y){int hh=find(x),hhh=find(y);faa[hh]=hhh;
}void Mtree(){for(int i=1;i<=m;i++) e[i].read();for(int i=1;i<=n;i++) faa[i]=i;for(int i=1;i<=m;i++){int x=e[i].from,y=e[i].to;if(find(x)!=find(y)){hebin(x,y);}}for(int i=2;i<=n;i++){if(find(1)!=find(i)){int hh=find(1),yy=find(i);e[++m].from=hh,e[m].to=yy,e[m].quan=-1;hebin(hh,yy);}}sort(e+1,e+m+1,comp);for(int i=1;i<=n;i++) faa[i]=i;numm=0;for(int i=1;i<=m;i++){int x=e[i].from,y=e[i].to,z=e[i].quan;int xx=find(x);int yy=find(y);if(xx!=yy){numm++;hebin(x,y);addedge(x,y,z),addedge(y,x,z);h[numm].from=x,h[numm].to=y,h[numm].quan=z;}if(numm==n-1) break;}
}void dfs1(int now,int f){fa[now]=f;size[now]=1;deep[now]=deep[f]+1;for(int i=a[now].first;i;i=a[i].next){int to=a[i].to;if(to==f) continue;dfs1(to,now);size[now]+=size[to];if(size[son[now]]<size[to]) son[now]=to;}
}void dfs2(int now,int rf){top[now]=rf;id[now]=++num;if(son[now]) dfs2(son[now],rf);for(int i=a[now].first;i;i=a[i].next){int to=a[i].to;if(to==fa[now]||to==son[now]) continue;dfs2(to,to);}
}void build(int xv,int l,int r){if(l==r){tr[xv].l=l,tr[xv].r=r;if(l==1) return;tr[xv].minn=w[l];return;}tr[xv].l=l,tr[xv].r=r;int mid=(l+r)/2;build(xv*2,l,mid);build(xv*2+1,mid+1,r);tr[xv].minn=min(tr[xv*2].minn,tr[xv*2+1].minn);
}int kanxun(int xv,int l,int r){int L=tr[xv].l,R=tr[xv].r,mid=(L+R)/2;if(l==L&&r==R){return tr[xv].minn;}if(r<=mid) return kanxun(xv*2,l,r);else if(l>mid) return kanxun(xv*2+1,l,r);else return min(kanxun(xv*2,l,mid),kanxun(xv*2+1,mid+1,r));
}int getmin(int x,int y){int topx=top[x],topy=top[y],minn=1<<30;while(topx!=topy){if(deep[topx]<deep[topy]) swap(x,y),swap(topx,topy);minn=min(kanxun(1,id[topx],id[x]),minn);x=fa[topx],topx=top[x];}if(x==y) return minn;if(deep[x]<deep[y]) swap(x,y);minn=min(minn,kanxun(1,id[son[y]],id[x]));return minn;
}int main(){cl();scanf("%d%d",&n,&m);Mtree();memset(fa,0,sizeof(fa));dfs1(1,0);num=0;dfs2(1,1);for(int i=1;i<=numm;i++){if(deep[h[i].from]>deep[h[i].to]) swap(h[i].from,h[i].to);int to=h[i].to,quan=h[i].quan;w[id[to]]=quan;}build(1,1,num);scanf("%d",&q);for(int i=1;i<=q;i++){int x,y;scanf("%d%d",&x,&y);printf("%d\n",getmin(x,y));}
}

?