其实就是要求最小的环套树森林

我们现在只考虑如何合并 设当前边的两个端点是x,y

若x,y在一个联通块里

那这个联通块要么是树 要么是环套树

假如是个环套树 加一条边后必定变成两个环 不符合要求

假如是个树 加一条边就变成了换套树 符合要求

若x,y不在一个联通块里

假如同为环套树 加一条边后必定变成两个环 不符合要求

假如同为树 加一条边后还是树 符合要求

假如一棵树 一棵环套树 加了过后变成环套树 符合要求

然后类似kruskal就好了

#include
    
     #define N 500005#define int long long using namespace std;struct data{    int x,y,z;}edge[2*N];int father[N];int n,m,tot,type[N];    //type=0 树 type=1 环 inline bool cmp(const data &a,const data &b){       return a.z
     
      >n>>m;    for(int i=1;i<=n;i++)   father[i]=i;    for(int i=1;i<=m;i++)    {        int x,y,z;        scanf("%d%d%d",&x,&y,&z);        addedge(x,y,z);    }    sort(edge+1,edge+tot+1,cmp);    int ans=0,cnt=0;    for(int i=1;i<=m;i++)    {        int fx=getfather(edge[i].x),fy=getfather(edge[i].y);        if(fx==fy)  //在一个联通块        {            if(type[fx]==0)//是个树             {                type[fx]=1; //他将变成环套树                 ans+=edge[i].z;                 ++cnt;            }             //环肯定是不能再加边的         }         else        {            if(type[fx]&&type[fy])  continue;   //两个环             father[fx]=fy;            type[fy]=type[fy]|type[fx];            ans+=edge[i].z;             ++cnt;         }    }    if(cnt!=n)  puts("No");    else cout<