标签：AcWing1143 int qquad 类边 无向 联络员 树中 边权

传送门

题目大意

\(\qquad\)给定一张无向图，其中无向图的边有两种类型：
\(\qquad\)\(\qquad\)\(1.\)这类边是必须选择的。
\(\qquad\)\(\qquad\)\(2.\)这类边是不必须选择的
\(\qquad\)求出这张图中所有生成树中包含所有第\(1\)类边的生成树中边权和最小的一棵的边权和

解题思路

\(\qquad\)我们可以利用\(Kruskal\)算法，思考一下，既然第\(1\)类边是必须选择的，那我们在读入的时候就直接把所有第\(1\)类边的权值加到我们的总边权中，并将它们统计到判断图是否连通的并查集里，然后照常做\(Kruskal\)就行。

代码

#include <iostream>
#include <algorithm>

using namespace std;

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

struct Edge 
{
    int u, v, w;
    bool operator <(const Edge& W) const {
        return w < W.w;
    }
} edge[N];

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

int Krus() 
{
    sort(edge + 1, edge + 1 + m);
    
    for (int i = 1; i <= m; i ++ ) 
    {
        int fu = find(edge[i].u), fv = find(edge[i].v);
        if (fu == fv) continue ;
        
        p[fu] = fv, res += edge[i].w;
    }
    
    return res;
}

int main() 
{
    scanf("%d%d", &n, &m);
    
    for (int i = 1; i <= n; i ++ ) p[i] = i;
    
    for (int i = 1; i <= m; i ++ ) 
    {
        int P, u, v, w;
        scanf("%d%d%d%d", &P, &u, &v, &w);
        if (P == 1) res += w, p[find(u)] = find(v);
        edge[i] = {u, v, w};
    }
    
    printf("%d\n", Krus());
    
    return 0;
}

\(\color{Green}{顺利AC！}\)

标签：AcWing1143,int,qquad,类边,无向,联络员,树中,边权
From： https://www.cnblogs.com/StkOvflow/p/17005770.html