洛谷 P1396 营救

张开发
• 2026/4/9 15:13:37 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

洛谷 P1396 营救
题目背景“咚咚咚……”“查水表”原来是查水表来了现在哪里找这么热心上门的查表员啊小明感动得热泪盈眶开起了门……题目描述妈妈下班回家街坊邻居说小明被一群陌生人强行押上了警车妈妈丰富的经验告诉她小明被带到了 t 区而自己在 s 区。该市有 m 条大道连接 n 个区一条大道将两个区相连接每个大道有一个拥挤度。小明的妈妈虽然很着急但是不愿意拥挤的人潮冲乱了她优雅的步伐。所以请你帮她规划一条从 s 至 t 的路线使得经过道路的拥挤度最大值最小。输入格式第一行有四个用空格隔开的 nmst其含义见【题目描述】。接下来 m 行每行三个整数 u,v,w表示有一条大道连接区 u 和区 v且拥挤度为 w。两个区之间可能存在多条大道。输出格式输出一行一个整数代表最大的拥挤度。输入输出样例输入 #1复制3 3 1 3 1 2 2 2 3 1 1 3 3输出 #1复制2说明/提示数据规模与约定对于 30% 的数据保证 n≤10。对于 60% 的数据保证 n≤100。对于 100% 的数据保证 1≤n≤1041≤m≤2×104w≤1041≤s,t≤n。且从 s 出发一定能到达 t 区。样例输入输出 1 解释小明的妈妈要从 1 号点去 3 号点最优路线为 1→2→3。#includebits/stdc.h using namespace std; //贪心并查集 const int N1e410,M2e410; typedef long long LL; LL n,m,s,t; struct node{ int u,v,w; }a[M]; int fa[N]; //并查集数组 bool cmp(node x,node y) { return x.wy.w; } int find(int x) { return fa[x]x?x:fa[x]find(fa[x]); } void un(int x,int y) { fa[find(x)]find(y); } int main() { cinnmst; for(int i1;im;i) { cina[i].ua[i].va[i].w; } sort(a1,a1m,cmp); for(int i1;in;i) { fa[i]i; } int reta[m].w; for(int i1;im;i) { int ua[i].u,va[i].v,wa[i].w; un(u,v); retw; if(find(s)find(t)) break; } coutretendl; return 0; }

更多文章