牛客练习赛69C

正题

题目链接:https://ac.nowcoder.com/acm/contest/7329/C

题目大意

d i s x , y dis_{x,y} disx,y​表示 x , y x,y x,y的所有路径的最短的边的最大值。
求一个 1 ∼ n 1sim n 1∼n的排列，使得 ∑ i = 2 n d i s i , i − 1 sum_{i=2}^ndis_{i,i-1} ∑i=2n​disi,i−1​最大

解题思路

首先一定是走在最大生成树上的路径
考虑两个已经确定路径的集合，现在合并这两个集合，因为是从大到小枚举的，所以对于合并的这条边显然是走的次数越少越好，那么显然最好是只走一次。

所以其实答案就是最大生成树的权值和。

c o d e code code

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=5e5+10; struct node{ll x,y,w; }a[N]; ll n,m,fa[N],ans; ll find(ll x) {return (fa[x]==x)?(x):(fa[x]=find(fa[x]));} bool cmp(node x,node y) {return x.w>y.w;} int main() {scanf("%lld%lld",&n,&m);for(ll i=1;i<=n;i++)fa[i]=i;for(ll i=1;i<=m;i++)scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].w);sort(a+1,a+1+m,cmp);ll t=n-1;for(ll i=1;i<=m;i++){ll x=find(a[i].x),y=find(a[i].y);if(x==y)continue;fa[x]=y;t--;ans+=a[i].w;if(!t)break;}printf("%lld",ans); }