惠州地区网站建设公司,网络运营培训班,vue做企业网站,自己做的网站怎么爬数据试题描述A 国有n座城市#xff0c;编号从1到n#xff0c;城市之间有m条双向道路。每一条道路对车辆都有重量限制#xff0c;简称限重。现在有q辆货车在运输货物#xff0c;司机们想知道每辆车在不超过车辆限重的情况下#xff0c;最多能运多重的货物。输入第一行有两个用一… 试题描述 A 国有n座城市编号从1到n城市之间有m条双向道路。每一条道路对车辆都有重量限制简称限重。现在有q辆货车在运输货物司机们想知道每辆车在不超过车辆限重的情况下最多能运多重的货物。 输入 第一行有两个用一个空格隔开的整数nm表示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 其他说明 数据范围0n10,0000m50,0000q30,0000≤z≤100,000。 这里用了某神犇论文中的解法。 首先做一遍最大生成树那么问题转化成了树上路径查询最小值我们考虑用按秩合并的并查集来做。 做最大生成树当合并节点xy时考虑将x的fa设为y并记录v[x]e[i].w。 那么询问时我们先判断两点是否在同一连通分量中然后因为按秩合并的树高最多是logn的暴力向上找并更新答案即可。 #includecstdio
#includecctype
#includequeue
#includecstring
#includealgorithm
#define rep(s,t) for(int is;it;i)
#define ren for(int ifirst[x];i!-1;inext[i])
using namespace std;
inline int read() {int x0,f1;char cgetchar();for(;!isdigit(c);cgetchar()) if(c-) f-1;for(;isdigit(c);cgetchar()) xx*10c-0;return x*f;
}
const int maxn50010;
struct Edge {int u,v,w;bool operator (const Edge ths) const {return wths.w;}
}e[maxn];
int n,m,q,pa[maxn],rk[maxn],v[maxn];
int findset(int x) {return xpa[x]?x:findset(pa[x]);}
int get(int x,int d) {if(xpa[x]) return x;d;return get(pa[x],d);
}
int main() {nread();mread();rep(1,n) pa[i]i;rep(1,m) e[i].uread(),e[i].vread(),e[i].wread();sort(e1,em1);rep(1,m) {int xfindset(e[i].u),yfindset(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];}}qread();while(q--) {int d10,d20,ans1e9;int xread(),yread();if(get(x,d1)get(y,d2)) {if(d1d2) swap(x,y),swap(d1,d2);rep(1,d1-d2) ansmin(ans,v[x]),xpa[x];while(x!y) {ansmin(ans,min(v[x],v[y]));xpa[x];ypa[y];}printf(%d\n,ans);}else puts(-1);}return 0;
} View Code 转载于:https://www.cnblogs.com/wzj-is-a-juruo/p/4624231.html
