试题描述 |
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。 |
输入示例 |
4 31 2 42 3 33 1 131 31 41 3 |
输出示例 |
3-13 |
其他说明 |
数据范围:0<n<10,000,0<m<50,000,0<q<30,000,0≤z≤100,000。 |
这里用了某神犇论文中的解法。
首先做一遍最大生成树,那么问题转化成了树上路径查询最小值,我们考虑用按秩合并的并查集来做。
做最大生成树当合并节点(x,y)时,考虑将x的fa设为y,并记录v[x]=e[i].w。
那么询问时我们先判断两点是否在同一连通分量中,然后因为按秩合并的树高最多是logn的,暴力向上找并更新答案即可。
#include#include #include #include #include #define rep(s,t) for(int i=s;i<=t;i++)#define ren for(int i=first[x];i!=-1;i=next[i])using namespace std;inline int read() { int x=0,f=1;char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f;}const int maxn=50010;struct Edge { int u,v,w; bool operator < (const Edge& ths) const { return w>ths.w;}}e[maxn];int n,m,q,pa[maxn],rk[maxn],v[maxn];int findset(int x) { return x==pa[x]?x:findset(pa[x]);}int get(int x,int& d) { if(x==pa[x]) return x;d++; return get(pa[x],d);}int main() { n=read();m=read(); rep(1,n) pa[i]=i; rep(1,m) e[i].u=read(),e[i].v=read(),e[i].w=read(); sort(e+1,e+m+1); rep(1,m) { int x=findset(e[i].u),y=findset(e[i].v); if(x!=y) { if(rk[x]>rk[y]) swap(x,y); pa[x]=y;v[x]=e[i].w;if(rk[x]==rk[y]) rk[y]++; } } q=read(); while(q--) { int d1=0,d2=0,ans=1e9; int x=read(),y=read(); if(get(x,d1)==get(y,d2)) { if(d1