分析

题目实际上是在要在给定的边上构建出一个树，使得这个树的最长边尽可能小。

这实际上是最小生成树的性质（反证法）。问题从而得到解决。

代码

/* * Code name => csp201812-5.cc * Written by Sam X * Date: 三月, 12, 2019 * Time: 10:13 */#include 
    
     #define fi first#define se second#define MP make_pair#define MS(x,y) memset(x, y, sizeof(x))#define ZERO(x) memset(x, 0, sizeof(x))#define rep(i,a,b)  for(repType i=static_cast
     
      (a); \                        i<=static_cast
      
       (b);++i)#define per(i,a,b)  for(repType i=static_cast
       
        (a); \                        i>=static_cast
        
         (b);--i)#define ALL(x) x.begin(), x.end()using repType=int;using ll=long long;using ld=long double;using namespace std;struct Edge{    int u,v,w;    Edge(int _u, int _v, int _w): u(_u), v(_v), w(_w) {}     bool operator < (const Edge& rhs) const    {        if(w!=rhs.w) return w
         
           edges; int n, m, root; cin>>n>>m>>root; iota(fa+1, fa+n+1, 1); rep(i, 1, m) { int u,v,w; cin>>u>>v>>w; edges.push_back(Edge(u,v,w)); } sort(ALL(edges)); int ans=0; rep(i,0,edges.size()-1) { if(fd(edges[i].u)!=fd(edges[i].v)) { ans=max(ans, edges[i].w); ue(edges[i].u, edges[i].v); } } cout<
          
           <