题目描述

对于两个集合a和b，每次扩充，最小值为w+1，边数最小值为s[a]*s[b]-1

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

const int N=6010;         

int p[N],s[N];
int n;

struct Edge
{
    int a,b;
    double w;

     bool operator< (const Edge &W)const
    {
        return w < W.w;
    }
}edge[N*N];



int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    else return x;
} 



int main()
{
    int T;
    cin>>T;
    while(T--)
    {
    cin>>n;
    //初始化
    for(int i=1;i<=n;i++)
    {
        p[i]=i;
        s[i]=1;
    }
    for(int i=1;i<=n-1;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        edge[i]={a,b,c};
    }

    sort(edge+1,edge+n);
    int res=0;
    for(int i=1;i<=n-1;i++)
    {
        int a=edge[i].a;
        int b=edge[i].b;
        int w=edge[i].w;

        a=find(a);
        b=find(b);
        if(a!=b)
        {
            res=res+(s[a]*s[b]-1)*(w+1);
            p[a]=b;
            s[b]+=s[a];
        }
    }


    cout<<res<<endl;


    }


    return 0;
}

二刷，最小生成树扩展为完全图的问题，要求最小边为w+1

s[a]*s[b]-1为需要加的边的数量(两个非连通图里点数之积再-w这条边)，w+1为加的边的权重的最小值

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

using namespace std;

const int N=6010;         

int p[N],s[N];
int n;

struct Edge
{
    int a,b;
    double w;

     bool operator< (const Edge &W)const
    {
        return w < W.w;
    }
}edge[N*N];


int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    else return x;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        cin>>n;
        memset(p,0,sizeof p);
        memset(s,0,sizeof s);
        for(int i=1;i<=n;i++)
        {
            p[i]=i;
            s[i]=1;
        }
        for(int i=1;i<=n-1;i++)
        {
            int a,b,c;
            cin>>a>>b>>c;
            edge[i]={a,b,c};
        }
        sort(edge+1,edge+n);
        int res=0;
        for(int i=1;i<=n-1;i++)
        {
            int a=edge[i].a;
            int b=edge[i].b;
            int w=edge[i].w;
            a=find(a);
            b=find(b);
            if(a!=b)
            {
                //s[a]*s[b]-1为需要加的边的数量(两个非连通图里点数之积再-w这条边)，w+1为加的边的权重的最小值
                res=res+(s[a]*s[b]-1)*(w+1);
                p[a]=b;
                s[b]+=s[a];

            }
        }
        cout<<res<<endl;
    }
    return 0;
}

三刷，还是不会 ，这题需要仔细复习

具体做法还是连通块与并查集的思想，包括kruscal的思想。
具体思路为：
1. 初始化连通块，s[i]保存第i个连通块含点的个数，初始为1
2. 把边从小到大排序，每次连接两个连通块，增加的边长度为w+1，边的个数为(s[a]*s[b]-1) 减去初始的一条边

#include <iostream>
#include <cstring>
#include <cmath>
#include<algorithm>

using namespace std;

const int N=10010;
int p[N],s[N];

struct edge
{
    int a,b,w;
    bool operator< (const edge &W) const
    {
        return w<W.w;
    }
}edges[N];

int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

int n,T;

int main()
{
    cin>>T;
    while(T--)
    {
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            //s[i]代表连通块里的点的个数
            s[i]=1;
            p[i]=i;
        }

        for(int i=1;i<=n-1;i++)
        {
            int a,b,c;
            cin>>a>>b>>c;
            edges[i]={a,b,c};
        }

        sort(edges+1,edges+n);
        int res=0;
        for(int i=1;i<=n-1;i++)
        {
            int a=edges[i].a;
            int b=edges[i].b;
            int w=edges[i].w;

            a=find(a);
            b=find(b);
            if(a!=b)
            {
                p[a]=b;
                res+=(w+1)*(s[a]*s[b]-1);
                s[b]+=s[a];
            }
        }
        cout<<res<<endl;

    }
    return 0;
}

四刷，想了一下思路，还是要用到最小生成树和连通块的思想

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N=100010;
int n,m,T;
int p[N];
int cnt[N];

int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

struct edge
{
    int a,b,w;
    bool operator< (const edge &W) const
    {
        return w<W.w;
    }
}edges[N];

int main()
{
    cin>>T;
    while(T--)
    {
        memset(p,0,sizeof p);
        memset(edges,0,sizeof edges);

        cin>>n;
        for(int i=1;i<=n;i++)
        {
            p[i]=i;
            cnt[i]=1;
        }
        for(int i=1;i<=n-1;i++)
        {
            int a,b,c;
            cin>>a>>b>>c;
            edges[i].a=a;
            edges[i].b=b;
            edges[i].w=c;
        }
        int res=0;
        sort(edges+1,edges+n);
        for(int i=1;i<=n-1;i++)
        {
            int a=edges[i].a;
            int b=edges[i].b;
            int c=edges[i].w;

            a=find(a);
            b=find(b);
            if(a!=b)
            {
                p[a]=b;
                res+=((cnt[b]*cnt[a]-1)*(c+1));
                cnt[b]+=cnt[a];
            }

        }
        cout<<res<<endl;

    }
    return 0;
}