编号    题目    状态    分数    总时间    内存    代码 / 答案文件    提交者    提交时间

 #    #. 「一本通 3.1 练习 」秘密的牛奶运输 Accepted         ms     KiB    C++ / 1.3 K    qwerta    -- ::

 #include<algorithm>

 #include<iostream>

 #include<cstdio>

 using namespace std;

 struct emm{

     int l,r,v,tag;

 }a[];

 bool cmp(emm qaq,emm qwq){

     return qaq.v<qwq.v;

 }

 int fa[];

 int fifa(int x)

 {

     if(fa[x]==x)return x;

     return fa[x]=fifa(fa[x]);

 }

 struct ahh{

     int e,f,v;

 }b[];

 int h[];

 int cnt=;

 void con(int x,int y,int len)//加边

 {

     b[++cnt].f=h[x];

     h[x]=cnt;

     b[cnt].e=y;

     b[cnt].v=len;

     b[++cnt].f=h[y];

     h[y]=cnt;

     b[cnt].e=x;

     b[cnt].v=len;

     return;

 }

 int MAX[][];//两点树上路径中边权最大值

 int s;

 void dfs(int x)//dfs找MAX[s][x]

 {

     for(int i=h[x];i;i=b[i].f)

     if(!MAX[s][b[i].e]&&b[i].e!=s)

     {

         MAX[s][b[i].e]=max(MAX[s][x],b[i].v);

         dfs(b[i].e);

     }

     return;

 }

 int main()

 {

     //freopen("a.in","r",stdin);

     int n,m;

     scanf("%d%d",&n,&m);

     for(int i=;i<=m;++i)

     {

         int x,y,z;

         scanf("%d%d%d",&x,&y,&z);

         a[i]=(emm){x,y,z};//建原图

     }

         //跑最小生成树

     for(int i=;i<=n;++i)

       fa[i]=i;

     sort(a+,a+m+,cmp);

     int k=n-,i=;

     long long now=;//记录最小生成树的边权和

     while(k)

     {

         ++i;

         int u=fifa(a[i].l),v=fifa(a[i].r);

         if(u!=v)

         {

             fa[u]=v;

             con(a[i].l,a[i].r,a[i].v);//建树图

             k--;

             now+=a[i].v;

             a[i].tag=;//标记为树边

         }

     }

     for(s=;s<=n;++s)

     {

         dfs(s);

     }

     long long ans=1e15;

     for(int i=;i<=m;++i)

     if(!a[i].tag&&a[i].v>MAX[a[i].l][a[i].r])//如果该边为非树边并且它的权值大于左右端点的树上距离（因为是次小生成树，所以权值要比最小生成树大

     {

         ans=min(ans,now-MAX[a[i].l][a[i].r]+a[i].v);//把路径上最大的换成这条边的答案

     }

     cout<<ans;

     return ;

 }