提出问题

俗话说的好，"想致富先修路"。现在有A、B、C、D、E、F总共6座城市，为了方便城市之间的贸易往来，市政府决定为这些城市修路，于是请你为他们设计一个合适的方案。为了贯彻中华民族勤俭节约的传统美德，需要你以最少的代价来设计，并且保证6个城市的连通性。

城市之间修路的代价如下：

image

~~3分钟时间思考（three minutes later）

问题分析

明确考图论。

首先我们要保证图的连通性。总共有6个结点，那么边的最少数量至少为6-1=5。又因为我们要尽量节约成本，所以我们只需要建立5条路径，满足图的连通性。即为一个无环连通图。

其次，我们该如何保证选中的这5条边在所有选择中总代价是最小的？

我们可以利用贪心的思想，每次选择权值最小的边，并且每次选择的时候判断这张子图是否否成环，若构成环则跳过，否则加入这条边。

那么问题来了，如何判环呢？

可以BFS/DFS、拓扑判环、并查集判环，有很多方法，这里往往选择并查集判环。
为什么并查集可以判环？
因为并查集本质上就是一个个集合，加入一条边后这两个顶点就加入了同一个集合，若发现两个顶点已然在同一个集合，那么自然出现了环。

解决问题

1. 根据边权将所有边进行排序

2. 选择最小边，并同时并查集判环

**并查集如何判环**

- 若属于同一集合，则会形成环

- 若不属于同一集合，则不会形成环

3. 检查终止条件：

- 添加的边数等于顶点数-1

- 所有边都被考虑过

代码

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
int pre[MAXN];

struct edge
{
    int u,v,cost;
    edge(int u,int v,int cost): u(u), v(v), cost(cost){};
};

bool cmp(edge e1, edge e2) {
    return e1.cost < e2.cost;
}

vector<edge> edges;

// 初始化并查集
void init(int n)
{
    for(int i = 1; i <= n; i ++){
        pre[i]=i;
    }
}

//寻找父节点
int find(int x) {
    if (pre[x]==x) return x;
    return pre[x]=find(pre[x]);
}

//合并
void unionsets(int a,int b) {
    a=find(a);
    b=find(b);
    if (a!=b) pre[a]=b;
}


void solve()
{
    int a,b,m,n;
    cin >> a >> b >> n >> m;

    memset(pre,-1,sizeof(pre));
    edges.clear();

    //初始化已经连通的结点
    for(int i = 1; i <= n; i ++){
        int u,v;
        cin >> u >> v;
        edges.push_back(edge(u, v, 0));
    }

    //录入可能连通的结点
    for(int i = 1; i <= m; i ++){
        int u, v, cost;
        cin >> u >> v >> cost;
    }

    // 利用克鲁斯卡尔算法生成最小树
    // 算法步骤：1.对边的权值(代价)进行排序 2.通过并查集判环

    sort(edges.begin(),edges.end(),cmp);

    //初始化并查集
    init(a+b+1);

    int maxn=-1;
    for(int i = 0; i < edges.size(); i ++){
        edge e=edges[i];
        //如果不在同一个集合，即不会形成回路
        if (find(e.u) != find(e.v)) {
            unionsets(e.u, e.v);
            maxn=max(maxn, e.cost);
        }
    }

    //生成树结束后，判断图的连通性。
    //若连通则输出maxn，否则输出-1
    int rt = find(1);
    for(int i = 2; i <= a+b; i ++){
        if (find(i) != rt) {
            cout << -1 << endl;
            return;
        }
    }
    cout << maxn << endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t=1;
    cin>>t;
    while(t--) solve();
    return 0;
}