本文共 1204 字，大约阅读时间需要 4 分钟。
题意：给你n个点，以及n-1条边和它的权值。定义S(i,j)为从i到j路径上权值最小的边的权值。求最大的 ∑S(i,j)。j从1到n。
思路：并查集。用point数组维护每一个集合的权值和点的个数，point[i][0]为权值，point[i][1]为集合点数。先将边降序排列。然后枚举每一条边，判断point[u][0]+w*point[v][1]和point[v][0]+w*point[u][1]的大小。如果前者大 就把v点所在集合并入u所在集合，然后把u集合的权值和点数更新，后者大就把u点所在集合并入v所在集合，然后把v集合的权值和点数更新。最后输出仅剩一个集合的权值。
#include #include #include #include #include #include #include #include #include #include using namespace std;typedef long long ll;const int MAXN=210000;struct Edge{ int u,v; ll w;}edge[210000];int n;ll point[MAXN][2];int par[MAXN];bool cmp(Edge a,Edge b){ return a.w>b.w;}int find(int x){ return x==par[x]?x:par[x]=find(par[x]);}void init(){ for(int i=0;i<=n;i++) par[i]=i,point[i][1]=1,point[i][0]=0;}int main(){ //freopen("in.txt","r",stdin); while(scanf("%d",&n)!=EOF) { init(); for(int i=0;i point[y][0]+w*point[x][1]) { par[y]=x; point[x][0]+=w*point[y][1]; point[x][1]+=point[y][1]; } else { par[x]=y; point[y][0]+=w*point[x][1]; point[y][1]+=point[x][1]; } } printf("%lld\n",point[find(1)][0]); } return 0;}
转载于:https://www.cnblogs.com/onlyAzha/p/4783955.html
