題目背景
NOIP2013 提高組 Day1 試題。
題目描述
A 國有 n 座城市,編号從 1 到 n,城市之間有 m 條雙向道路。每一條道路對車輛都有重量限制,簡稱限重。現在有 q 輛貨車在運輸貨物,司機們想知道每輛車在不超過車輛限重的情況下,最多能運多重的貨物。
輸入格式
第一行有兩個用一個空格隔開的整數 n ,m,表示 A 國有 n 座城市和 m 條道路。
接下來 m 行每行 3 個整數 x、y、z,每兩個整數之間用一個空格隔開,表示從 x 号城市到 y 号城市有一條限重為 z 的道路。注意:x 不等于 y,兩座城市之間可能有多條道路。
接下來一行有一個整數 q,表示有 q 輛貨車需要運貨。
接下來 q 行,每行兩個整數 x、y,之間用一個空格隔開,表示一輛貨車需要從 x 城市運輸貨物到 y 城市,注意:x 不等于 y。
輸出格式
輸出共有 q 行,每行一個整數,表示對于每一輛貨車,它的最大載重是多少。如果貨車不能到達目的地,輸出 -1。
樣例資料 1
輸入
4 3
1 2 4
2 3 3
3 1 1
3
1 3
1 4
1 3
輸出
3
-1
3
備注
【資料範圍】
對于 30% 的資料,0<n<1,000 ;0<m<10,000 ;0<q<1,000;
對于 60% 的資料,0<n<1,000 ;0<m<50,000 ;0<q<1,000;
對于 100% 的資料,0<n<10,000 ;0<m<50,000 ;0<q<30,000 ;0≤z≤100,000。
解析:
額最初方向想偏了,當時把題目問題轉化成求圖中兩點間路徑中最小邊權的最大值,雖然是對的但是根本不好處理,于是GG。。。
看了題解才意識到,因為貨車要運盡可能多的貨,就應該盡可能走承受力較大的路。是以如果這兩個點聯通,貨車一定是在這些點構成的最大生成樹上行走,于是就把圖的問題轉化為樹上的問題,于是隻用求兩點間最短路徑中邊權最小值,直接倍增求就行了。
代碼:
#include <bits/stdc++.h>
using namespace std;
const int Maxn=10005;
const int Maxm=50005;
int n,m,q,size;
int first[Maxn],f[Maxn][18],d[Maxn][18],depth[Maxn],father[Maxn],vis[Maxn];
struct shu{int to,next,len;};
shu edge[Maxm<<1];
struct kru{int x,y,len;};
kru a[Maxm<<1];
inline int get_int()
{
int x=0,f=1;
char c;
for(c=getchar();(!isdigit(c))&&(c!='-');c=getchar());
if(c=='-') f=-1,c=getchar();
for(;isdigit(c);c=getchar()) x=(x<<3)+(x<<1)+c-'0';
return x*f;
}
inline void print(int x)
{
if(x>9) print(x/10);
putchar('0'+x%10);
}
inline bool comp(const kru &a,const kru &b){return a.len>b.len;}
inline int get(int v){return father[v]==v ? v : father[v]=get(father[v]);}
inline void build(int x,int y,int z)
{
edge[++size].next=first[x];
first[x]=size;
edge[size].to=y,edge[size].len=z;
}
inline void dfs(int point,int fa)
{
for(int i=1;i<=16;i++)
if(depth[point]>=(1<<i))
{
f[point][i]=f[f[point][i-1]][i-1];
d[point][i]=min(d[point][i-1],d[f[point][i-1]][i-1]);
}
else break;
for(int u=first[point];u;u=edge[u].next)
{
int to=edge[u].to;
if(to==fa) continue;
f[to][0]=point,d[to][0]=edge[u].len,depth[to]=depth[point]+1;
dfs(to,point);
}
}
inline int LCA(int x,int y)
{
if(depth[x] < depth[y]) swap(x,y);
int len=depth[x]-depth[y];
for(int i=16;i>=0;i--)
if(len>=(1<<i)) len-=1<<i,x=f[x][i];
if(x==y) return x;
for(int i=16;i>=0;i--)
if(f[x][i]!=f[y][i]) x=f[x][i],y=f[y][i];
return f[x][0];
}
inline int search(int x,int fa)
{
int len=depth[x]-depth[fa],minn=1e9;
for(int i=16;i>=0;i--)
if(len>=(1<<i))
len-=1<<i,minn=min(minn,d[x][i]),x=f[x][i];
return minn;
}
inline int solve(int x,int y)
{
int fa=LCA(x,y);
return min(search(x,fa),search(y,fa));
}
int main()
{
n=get_int(),m=get_int();
for(int i=1;i<=n;i++) father[i]=i;
for(int i=1;i<=m;i++) a[i].x=get_int(),a[i].y=get_int(),a[i].len=get_int();
sort(a+1,a+m+1,comp);
for(int i=1;i<=m;i++)
if(get(a[i].x)!=get(a[i].y))
father[get(a[i].x)]=get(a[i].y),build(a[i].x,a[i].y,a[i].len),build(a[i].y,a[i].x,a[i].len);
q=get_int();
for(int i=1;i<=n;i++) if(!vis[get(i)]) vis[get(i)]=1,dfs(i,0);
while(q--)
{
int x=get_int(),y=get_int();
if(get(x)!=get(y)) cout<<"-1\n";
else print(solve(x,y)),putchar('\n');
}
return 0;
}