有必选边，先把必选边加入集合，再做kruskal；

必选边加入集合要注意是p[find(a)]=find(b)

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

using namespace std;

const int N=2010;
const int M=10010;
int n,m,p[N];

struct Edge
{
    int a,b,w;

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

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


int main()
{
    int res=0;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        p[i]=i;

    }
    int k=1;
    for(int i=1;i<=m;i++)
    {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        if(a==1)
        {
            //edge[i]={b,c,d};
            p[find(b)]=find(c);
            res+=d;
        }
        else
        {
            edge[k++]={b,c,d};
        }

    }
    sort(edge+1,edge+k+1);
    for(int i=1;i<=k;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)
        {
            p[a]=b;
            res+=w;
        }
    }
    cout<<res;
    return 0;
}

二刷，注意find函数有个坑

如果find写成下面这种形式，可以过

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

这样也可以过

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

但这样不行

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

最终模板！！

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

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

using namespace std;

const int N=2010;
const int M=10010;
int n,m,p[N];

struct Edge
{
    int a,b,w;

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

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

int main()
{
    cin>>n>>m;
    int cnt=1;
    int res=0;
    for(int i=1;i<=n;i++)
    {
        p[i]=i;
    }
    for(int i=1;i<=m;i++)
    {
        int a,b,c,q;
        cin>>q>>a>>b>>c;
        if(q==1)
        {
            a=find(a);
            b=find(b);
            p[a]=b;
            res+=c;
        }
        else
        {
            edge[cnt++]={a,b,c};
        }
    }

    sort(edge+1,edge+cnt+1);
    for(int i=1;i<=cnt;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)
        {
            p[a]=b;
            res+=w;
        }
    }
    cout<<res;


    return 0;
}

三刷，很简单的ac了，有必选边的kruscal

做法为先将必选边假如并查集，但是不必把必选边加入edges[N]中，
edges只需要保存非必选边

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

using namespace std;

const int N=100010;

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

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

int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        p[i]=i;
    }
    int res=0;
    int j=0;
    for(int i=1;i<=m;i++)
    {
        int a,b,c,d;
        cin>>a>>b>>c>>d;
        if(a==1)
        {
            b=find(b);
            c=find(c);
            p[b]=c;
            res+=d;

        }
        else
        {
            edges[++j]={b,c,d};
        }
    }
    sort(edges+1,edges+j+1);
    for(int i=1;i<=j;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;
        }
    }

    cout<<res;
    return 0;
}

2023/12/22

先将必选边加入集合，有一个坑：
在选必选边时，即使a和b两个点已经在集合中，也要加上cost

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

using namespace std;

const int N=100010;

int p[N], cnt[N];
int n,m;

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

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

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        p[i] = i;
    }

    int res_cnt=0;
    int res_cost=0;
    for(int i=1;i<=m;i++)
    {
        int q,a,b,c;
        cin>>q>>a>>b>>c;
        edges[i].a = a;
        edges[i].b = b;
        edges[i].w = c;

        // 如果是必选边，则将必选边先加入集合
        if(q==1)
        {
            a = find(a);
            b = find(b);

            if(a!=b)
            {
                p[a] = b;
                res_cnt ++;
            }
            res_cost+=c;
        }
    }

    sort(edges+1, edges+1+m);

    for(int i=1;i<=m;i++)
    {
        int a = edges[i].a;
        int b = edges[i].b;
        int c = edges[i].w;

        a = find(a);
        b = find(b);

        if(res_cnt == m-1)
        {
            break;
        }

        if(a!=b)
        {
            p[a] = b;
            res_cost+=c;
            res_cnt ++;
        }
    }


    cout<<res_cost;
    return 0;
}