Tyvj已经一岁了，网站也由最初的几个用户增加到了上万个用户，随着Tyvj网站的逐步壮大，管理员的数目也越来越多，现在你身为Tyvj管理层的联络员，希望你找到一些通信渠道，使得管理员两两都可以联络（直接或者是间接都可以）。Tyvj是一个公益性的网站，没有过多的利润，所以你要尽可能的使费用少才可以。

目前你已经知道，Tyvj的通信渠道分为两大类，一类是必选通信渠道，无论价格多少，你都需要把所有的都选择上；还有一类是选择性的通信渠道，你可以从中挑选一些作为最终管理员联络的通信渠道。数据保证给出的通行渠道可以让所有的管理员联通。

第一行n，m表示Tyvj一共有n个管理员，有m个通信渠道;

第二行到m+1行，每行四个非负整数，p,u,v,w 当p=1时，表示这个通信渠道为必选通信渠道；当p=2时，表示这个通信渠道为选择性通信渠道；u,v,w表示本条信息描述的是u，v管理员之间的通信渠道，u可以收到v的信息，v也可以收到u的信息，w表示费用。

最小的通信费用。

5 6
1 1 2 1
1 2 3 1
1 3 4 1
1 4 1 1
2 2 5 10
2 2 5 5

9

【样例解释】

1-2-3-4-1存在四个必选渠道，形成一个环，互相可以到达。需要让所有管理员联通，需要联通2号和5号管理员，选择费用为5的渠道，所以总的费用为9。

【注意】

U,v之间可能存在多条通信渠道，你的程序应该累加所有u,v之间的必选通行渠道

【数据范围】

对于30%的数据，n≤10,m≤100;

对于50%的数据, n≤200,m≤1000

对于100%的数据，n≤2000,m≤10000

1. 题目背景与分析

题目描述：

Tyvj 网站要建立管理员之间的通信网络。共有N个管理员和M个通信渠道。

渠道分为两类：

1. 必选渠道 (p=1)：必须建立连接，无论代价如何。

2. 可选渠道 (p=2)：可以从中挑选，用于补充连接。

目标：让所有管理员联通（直接或间接），并使总费用最小。

核心模型：

这道题本质上是一个最小生成树 (MST) 的变种问题。

普通的 MST 是从一张空白图开始选边；而这道题相当于图上已经预先连接了一些边（甚至可能形成了环或者多个连通块），我们需要在现有的基础上，用最小的代价把剩下的部分连通起来。

---

2. 算法选择：Kruskal

对于这类“存在必选边”或“混合图”问题，Kruskal 算法几乎是唯一推荐的解法，而Prim算法在这里会非常棘手。

为什么选 Kruskal？

Kruskal 算法的核心逻辑是维护“森林”（并查集）。

• 天然契合：我们可以先处理所有必选边，直接在并查集中进行合并。这相当于游戏还没开始，几个小团体就已经组好了。

• 无视环与连通块：必选边如果构成了环，或者构成了多个互不相连的连通块，Kruskal 完全不在乎。它只需要在剩下的边里，挑出能连接不同集合的边即可。

为什么Prim不好做？

Prim算法的核心是从一个点开始长出一棵树。

1. 森林困境：必选边可能把图分成了几个不连通的“岛屿”。Prim从一个岛出发，无法跨越到另一个岛（除非把整个岛缩成一个点，但这太复杂了）。

2. 环的处理：题目提示“必选渠道可能形成环”。Prim 维护的是距离数组，如果初始结构就有环，Prim的更新逻辑会非常混乱。

---

3. 解题策略

1. 分离处理：

   • 读取数据时，如果是 必选边 (p=1)：直接调用并查集的uni(u, v) 进行合并，并将费用直接累加到总答案sum中。注意：这些边不需要加入待排序的数组中。

   • 如果是 可选边 (p=2)：存入边集数组 e[]，等待后续排序和挑选。

2. 排序与遍历：

   • 对 e[] 数组按权值从小到大排序。

   • 执行标准的Kruskal流程：遍历数组，如果 find(u)!=find(v)，说明这条边能连接两个尚未连通的板块，选中它并累加费用。

---

4. 完整代码 

//kruskal
#include <iostream>
#include <algorithm>//对应sort函数
using namespace std;
long long sum;//最小生成树长度（总通信费用）
int n,m;
int fa[2100];//每个节点的父/祖先节点
struct edge{
    int u,v,w;
    //重载运算符，按费用从小到大排序
    friend bool operator<(edge a,edge b){
        return a.w<b.w;
    }
}e[10010];//边集数组
int cnt;//记录边集数组的边数

//并查集查询+路径压缩
int find(int x){
    if(fa[x]==x) return x;//如果是根节点就返回
    //否则就递归找根节点 并把根节点赋值给沿途所有节点
    return fa[x]=find(fa[x]);
}

void uni(int a,int b){
    int faa=find(a);//a集合中的老大
    int fab=find(b);//b集合中的老大
    if(faa!=fab){//如果老大不同
        fa[fab]=faa;//就让a的老大成为b的老大的老大的父亲
    }
}

void kruskal(){
    for(int i=1;i<=cnt;i++){
        int a=e[i].u;
        int b=e[i].v;
        if(find(a)!=find(b)){//如果ab不在一个集合
            sum+=e[i].w;
            uni(a,b);
        }
    }
}

int main(){
    cin>>n>>m;
    //初始化每个节点自成集合
    for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++){
        int p,u,v,w;
        cin>>p>>u>>v>>w;
        if(p==1){//必选通信渠道
            uni(u,v);
            sum+=w;
        }
        else{
            e[++cnt].u=u;
            e[cnt].v=v;
            e[cnt].w=w;
        }
    }
    sort(e+1,e+cnt+1);//边集数组按从小到大排序
    kruskal();
    cout<<sum;
    return 0;
}

5. 总结

这道题是Kruskal算法灵活运用的典范。

• 遇到“必选边”、“已经存在的路”这类条件，直接在并查集初始化阶段处理掉。

• 遇到“可选边”、“新建的路”，才放入算法流程中去贪心选择。

• 这种“并查集预处理 + 贪心”的模式，是解决混合图连通性问题的好方法。