題目描述
AAA國有nn n座城市,編号從 11 1到n nn,城市之間有 mmm 條雙向道路。每一條道路對車輛都有重量限制,簡稱限重。現在有 qqq 輛貨車在運輸貨物, 司機們想知道每輛車在不超過車輛限重的情況下,最多能運多重的貨物。
輸入輸出格式
輸入格式:
第一行有兩個用一個空格隔開的整數n,m n,mn,m,表示 AAA 國有n nn 座城市和 mmm 條道路。
接下來 mmm行每行3 3 3個整數 x,y,zx, y, zx,y,z,每兩個整數之間用一個空格隔開,表示從 xx x号城市到y y y号城市有一條限重為 zzz 的道路。注意: xxx 不等于 yyy,兩座城市之間可能有多條道路 。
接下來一行有一個整數 q,表示有 q 輛貨車需要運貨。
接下來 q 行,每行兩個整數 x、y,之間用一個空格隔開,表示一輛貨車需要從 x 城市運輸貨物到 y 城市,注意: x 不等于 y 。
輸出格式:
共有 qqq 行,每行一個整數,表示對于每一輛貨車,它的最大載重是多少。如果貨車不能到達目的地,輸出−1-1−1。
輸入輸出樣例
輸入樣例#1:
複制
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
輸出樣例#1: 複制
3
-1
3
說明
對于 30%30\%30%的資料,0<n<1,000,0<m<10,000,0<q<1,0000 < n < 1,000,0 < m < 10,000,0 < q< 1,0000<n<1,000,0<m<10,000,0<q<1,000;
對于 60%60\%60%的資料,0<n<1,000,0<m<50,000,0<q<1,0000 < n < 1,000,0 < m < 50,000,0 < q< 1,0000<n<1,000,0<m<50,000,0<q<1,000;
對于 100%100\%100%的資料,0<n<10,000,0<m<50,000,0<q<30,000,0≤z≤100,0000 < n < 10,000,0 < m < 50,000,0 < q< 30,000,0 ≤ z ≤ 100,0000<n<10,000,0<m<50,000,0<q<30,000,0≤z≤100,000。
題解:哦,這題是多麼睿智啊,未來又可以多出一段梗了
有一回對我說道,“你學過OI嗎麼?”我略略點一點頭。他說,“學過OI,……我便考你一考。2013年提高組的D1T3,怎樣寫的?”
我想,讨飯一樣的人,也配考我麼?便回過臉去,不再理會。
孔乙己等了許久,很懇切的說道,“不能寫罷?……我教給你,記着!這些題應該記着。将來打比賽的時候,賀題要用。”
我暗想我和打模拟賽的水準還很遠呢,而且我們比賽也從不将原題上賬;又好笑,又不耐煩,懶懶的答他道,“誰要你教,不是最大生成樹上跑跑倍增嘛?”
孔乙己顯出極高興的樣子,将兩個指頭的長指甲敲着鍵盤,點頭說,“對呀對呀!……這道題有四樣寫法,你知道麼?”
我愈不耐煩了,努着嘴走遠。孔乙己剛解了鎖屏,想在電腦上寫題,見我毫不熱心,便又歎一口氣,顯出極惋惜的樣子。
反正原來的做法就是最大生成樹上跑跑lca,過程中順便記錄一下答案(lca至少有四種求法,不接受任何反駁╭(╯^╰)╮)
但我仔細一思索這題好像克魯斯卡爾重構樹也能做,大概做法就是建出一顆重構樹以後輸出詢問兩點之間的lca就可以啦
代碼如下:
#include<bits/stdc++.h>
using namespace std;
vector<int> g[60060];
struct edge
{
int from,to,val;
}e[50050];
int fa[100010],n,m,cnt,v[100010],deep[100010],f[100010][18];
int cmp(edge x,edge y)
{
return x.val>y.val;
}
int init()
{
for(int i=1;i<=100000;i++)
{
fa[i]=i;
}
}
int find(int x)
{
if(fa[x]==x) return x;
return fa[x]=find(fa[x]);
}
int union_(int x,int y,int val)
{
int fx=find(x);
int fy=find(y);
if(fx==fy) return 0;
fa[fx]=fa[fy]=++cnt;
g[fx].push_back(cnt);
g[cnt].push_back(fx);
g[fy].push_back(cnt);
g[cnt].push_back(fy);
v[cnt]=val;
}
int dfs(int now,int fat,int dep)
{
f[now][0]=fat;
deep[now]=dep;
for(int i=1;i<=17;i++) f[now][i]=f[f[now][i-1]][i-1];
for(int i=0;i<g[now].size();i++)
{
if(g[now][i]==fat) continue;
dfs(g[now][i],now,dep+1);
}
}
int lca(int x,int y)
{
if(deep[x]<deep[y]) swap(x,y);
for(int i=17;i>=0;i--) if(deep[f[x][i]]>=deep[y]) x=f[x][i];
if(x==y) return x;
for(int i=17;i>=0;i--) if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
int main()
{
init();
int from,to;
scanf("%d%d",&n,&m);
cnt=n;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d",&e[i].from,&e[i].to,&e[i].val);
}
sort(e+1,e+m+1,cmp);
for(int i=1;i<=m;i++)
{
union_(e[i].from,e[i].to,e[i].val);
}
for(int i=1;i<=cnt;i++)
{
if(find(i)==i) dfs(i,0,1);
}
int ttt;
scanf("%d",&ttt);
while(ttt--)
{
scanf("%d%d",&from,&to);
int anc=lca(from,to);
if(anc) printf("%d\n",v[anc]);
else puts("-1");
}
}