C 旅行

C 旅行

• 最小生成树能够保证首先是树（对于个顶点的图只有条边），其次保证任意两个顶点之间都可达，再次保证这棵树的边权值之和为最小，但不能保证任意两点之间是最短路径；（最后求出来的路径长度是经过n个顶点的)
• 最短路保证从源点到目地点的路径最小（有向图中不要求终点能到起点），不保证任意两个顶点都可达;(最后求出来的路径长度不一定过n个顶点）
• 最小生成树是到一群点（所有点）的路径代价和最小，是一个条边的树，最短路是从一个点到另一个点的最短路径；

这里是求最大路径,要经过个顶点

那就是最大生成树，把里的符号改一下就好了，变成从大到小的顺序。

#include <bits/stdc++.h>
#define rep(i,x,y) for (int i=(x);i<=(y);i++)
using namespace std;
typedef long long ll;
const int maxn=1e6+10;
ll n,m,u,v,w,ans,cnt;

ll fa[maxn];

struct sa{
    ll u,v,w;
}e[maxn];

bool cmp(struct sa x,struct sa y){
    return x.w>y.w;
}

ll find(ll x) {
    if(fa[x] == x) return x;
    return fa[x] = find(fa[x]);
}

int main()
{
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin>>n>>m;
    rep(i,1,m) cin>>e[i].u>>e[i].v>>e[i].w;
    sort(e+1,e+1+m,cmp);
    rep(i,1,n) fa[i]=i;
    rep(i,1,m){
        if(cnt==n-1) break;
        w=e[i].w; u=find(e[i].u);v=find(e[i].v);
        if(u!=v){
            fa[u]=v;
            ans+=w;
            cnt++;
        }
    }
    cout<<ans<<endl;
    return 0;
}