Daleks' Invasion
2026-04-17 22:06:13
发布于：上海
12阅读
0回复
0点赞
CF1184E1 Daleks' Invasion (easy)
题目描述
Heidi 发现 Daleks 创建了一个由双向时间通道连接不同目的地（在不同时间！）的网络。她怀疑他们正计划对整个时空进行又一次入侵。为了反制入侵，她打算在时间漩涡中沿着精心挑选的时间通道布置陷阱。她知道干涉时间漩涡很危险，于是咨询了 Doctor 的意见。她了解到如下信息：
- 不同的时间通道需要不同的能量来保持稳定。
- Daleks 在入侵时不太可能使用所有通道。他们会选择一组总能量消耗最小、但仍能保证任意两个目的地之间可以（通过时间）到达的通道（对于熟悉的人来说：他们会选择一棵最小生成树）。
- 布置陷阱可能会改变该通道所需的能量。
Heidi 决定进行实地测试，并在第一条通道上布置一个陷阱。但她需要知道，在布置陷阱后 Daleks 是否还会使用这条通道。
她给了你一张时间通道的地图（一个无向图），每条通道都有对应的能量需求。
对于一条通道 ， 表示最大的 ，使得如果我们将 的能量需求改为 ，那么 Daleks 仍有可能在入侵时使用 （即 属于某棵最小生成树）。你的任务是计算 Heidi 计划布置陷阱的第一条通道 的 。
输入格式
第一行包含两个整数 和 （，），分别表示目的地数量和时间通道数量。
接下来的 行，每行描述一条通道：目的地 、 以及能量 （，，）。
保证没有重复的 对，并且图是连通的——即任意两个目的地之间都可以通过若干条时间通道到达。
输出格式
输出一个整数：第一条通道 的 。
输入输出样例 #1
输入 #1
3 3
1 2 8
2 3 3
3 1 4
输出 #1
4
说明/提示
布置陷阱后，第一条通道的能量需求可能变小、变大或保持不变。
例如，在样例中，如果第一条通道的能量被设置为 或更小，则 Daleks 可能会选择通道集合 （特别地，如果设置为小于 ，那么这将是唯一的选择）。然而，如果能量大于 ，他们则会选择通道集合 。
答案：
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int M=1e6+10;
struct Edge{
int x,y,z;
}edges[M];
int fa[N],n,m,choose,ans=1e9;
int get(int x){
if(fa[x]==x) return x;
return fa[x]=get(fa[x]);
}
void merge(int x,int y){
fa[get(x)]=get(y);
}
bool cmp(Edge A,Edge B){
return A.z<B.z;
}
int main(){
cin>>n>>m;
for(int i=1;i<=m;i++)
cin>>edges[i].x>>edges[i].y>>edges[i].z;
sort(edges+2,edges+m+1,cmp);
for(int i=1;i<=n;i++)
fa[i]=i;
for(int i=2;i<=m;i++){
if(get(edges[i].x)==get(edges[i].y)) continue;
merge(edges[i].x,edges[i].y);
choose++;
if(get(edges[1].x)==get(edges[1].y)){
ans=edges[i].z;
break;
}
}
cout<<ans;
return 0;
}
有帮助，赞一个