巴州建设局网站,企业画册设计制作公司,长沙人力资源招聘网,外贸公司网站搭建正题
题目链接:https://ac.nowcoder.com/acm/contest/7329/C 题目大意 disx,ydis_{x,y}disx,y表示x,yx,yx,y的所有路径的最短的边的最大值。 求一个1∼n1\sim n1∼n的排列#xff0c;使得∑i2ndisi,i−1\sum_{i2}^ndis_{i,i-1}∑i2ndisi,i−1最大 解题思路
首先一定是…正题
题目链接:https://ac.nowcoder.com/acm/contest/7329/C 题目大意
disx,ydis_{x,y}disx,y表示x,yx,yx,y的所有路径的最短的边的最大值。 求一个1∼n1\sim n1∼n的排列使得∑i2ndisi,i−1\sum_{i2}^ndis_{i,i-1}∑i2ndisi,i−1最大 解题思路
首先一定是走在最大生成树上的路径 考虑两个已经确定路径的集合现在合并这两个集合因为是从大到小枚举的所以对于合并的这条边显然是走的次数越少越好那么显然最好是只走一次。
所以其实答案就是最大生成树的权值和。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N5e510;
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.wy.w;}
int main()
{scanf(%lld%lld,n,m);for(ll i1;in;i)fa[i]i;for(ll i1;im;i)scanf(%lld%lld%lld,a[i].x,a[i].y,a[i].w);sort(a1,a1m,cmp);ll tn-1;for(ll i1;im;i){ll xfind(a[i].x),yfind(a[i].y);if(xy)continue;fa[x]y;t--;ansa[i].w;if(!t)break;}printf(%lld,ans);
}
