企业网站 优帮云,做网站字体要求,餐饮众筹模板网站建设,wordpress智能表单题目描述 Description A 国有 n 座城市#xff0c;编号从 1 到 n#xff0c;城市之间有 m 条双向道路。每一条道路对车辆都有重量限制#xff0c;简称限重。现在有 q 辆货车在运输货物#xff0c;司机们想知道每辆车在不超过车辆限重的情况下#xff0c;最多能运多重的货物… 题目描述 Description A 国有 n 座城市编号从 1 到 n城市之间有 m 条双向道路。每一条道路对车辆都有重量限制简称限重。现在有 q 辆货车在运输货物司机们想知道每辆车在不超过车辆限重的情况下最多能运多重的货物。 输入描述 Input Description 第一行有两个用一个空格隔开的整数 nm表示 A 国有 n 座城市和 m 条道路。接下来 m 行每行 3 个整数 x、y、z每两个整数之间用一个空格隔开表示从 x 号城市到 y 号城市有一条限重为 z 的道路。注意x 不等于 y两座城市之间可能有多条道路。接下来一行有一个整数 q表示有 q 辆货车需要运货。接下来 q 行每行两个整数 x、y之间用一个空格隔开表示一辆货车需要从 x 城市运输货物到 y 城市注意x 不等于 y。 输出描述 Output Description 输出共有 q 行每行一个整数表示对于每一辆货车它的最大载重是多少。如果货车不能到达目的地输出-1。 样例输入 Sample Input 4 31 2 42 3 33 1 131 31 41 3 样例输出 Sample Output 3-13 数据范围及提示 Data Size Hint 对于 30%的数据0 n 1,0000 m 10,0000 q 1,000对于 60%的数据0 n 1,0000 m 50,0000 q 1,000对于 100%的数据0 n 10,0000 m 50,0000 q 30,0000 ≤ z ≤ 100,000。 题解 最大生成树LCA 1 #includeiostream2 #includecstdio3 #includecstdlib4 #includecmath5 #includealgorithm6 #includecstring7 #includevector8 #includequeue9 using namespace std;10 const int maxn10005;11 const int maxm50005;12 int N,M,Q;13 vectorint to[maxn],cost[maxn];14 int p[maxn][50],next[maxn][50];15 int dep[maxn];16 int fa[maxn];17 struct node{18 int uu,vv,cc;19 }a[maxm];20 int cmp(const nodeq,const nodew){21 if(q.ccw.cc) return 1;22 return 0;23 }24 inline int get_fa(int x){25 if(x!fa[x]) fa[x]get_fa(fa[x]);26 return fa[x];27 }28 inline void dfs(int x){29 for(int i0;ito[x].size();i){30 int yto[x][i];31 if(y!p[x][0]){32 dep[y]dep[x]1;33 p[y][0]x;34 next[y][0]cost[x][i];35 for(int k1;k30;k){36 int zu1k;37 if(zudep[y]){38 p[y][k]p[p[y][k-1]][k-1];39 next[y][k]min(next[y][k-1],next[p[y][k-1]][k-1]);40 }41 else break;42 } 43 dfs(y);44 }45 }46 }47 inline int LCA(int x,int y){48 int ANS1e9;49 if(dep[x]dep[y]) swap(x,y);50 int deltadep[y]-dep[x];51 for(int i0;i30;i){52 int h1i; hhdelta;//这步很关键如果直接用 if((1i)delta!0) 会出错 53 if(h!0){54 ANSmin(ANS,next[y][i]);55 yp[y][i];56 }57 }58 if(xy) return ANS;59 for(int i30;i0;i--){60 if(p[x][i]!p[y][i]){61 ANSmin(ANS,next[x][i]); ANSmin(ANS,next[y][i]);62 xp[x][i]; yp[y][i];63 }64 }65 ANSmin(ANS,next[y][0]); ANSmin(ANS,next[x][0]);66 return ANS;67 }68 int main(){69 // freopen(truck.in,r,stdin);70 // freopen(truck.out,w,stdout);71 scanf(%d%d,N,M);72 for(int i1;iN;i) fa[i]i;73 for(int i1;iM;i){74 int u,v,c;75 scanf(%d%d%d,u,v,c);76 a[i].uuu; a[i].vvv; a[i].ccc;77 }78 sort(a1,aM1,cmp);79 for(int i1;iM;i){80 int ua[i].uu; int va[i].vv; int ca[i].cc;81 int fauget_fa(u); int favget_fa(v);82 if(fau!fav){83 if(faufav) fa[fav]fau;84 else fa[fau]fav;85 to[u].push_back(v); to[v].push_back(u);86 cost[u].push_back(c); cost[v].push_back(c);87 }88 }89 p[1][0]-1; dep[1]0;90 dfs(1);91 scanf(%d,Q);92 for(int i1;iQ;i){93 int u,v;94 scanf(%d%d,u,v);95 int nowLCA(u,v);96 if(now0) now-1;97 coutnowendl;98 }99 return 0;
100 } 转载于:https://www.cnblogs.com/CXCXCXC/p/4938461.html
