数据结构算法——1095. 公路村村通

数据结构算法——1095. 公路村村通 题目

输入
6 15
1 2 5
1 3 3
1 4 7
1 5 4
1 6 2
2 3 4
2 4 6
2 5 2
2 6 6
3 4 6
3 5 1
3 6 1
4 5 10
4 6 8
5 6 3

输出
12

思路

经典并查集，生成最小生成树

代码

#include
#include
#include
using namespace std;

struct node
{
    int start, end, cost;
};
bool operator<(const node& l, const node& r)
{return l.cost < r.cost;};
//这里要重载一下等会sort要用

int father[1200];
int find(int x)
{
    if(x == father[x])  return x;
    return father[x] = find(father[x]);
}
void U(int x, int y)
{
    father[find(x)] = find(y);
}
int ask(int x, int y)
{
    return(find(x) == find(y));
}
//邻接表三件套
int main()
{
    int n,m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        father[i] = i;
    vector v;
    for(int i = 0; i < m; i++)
    {
        int start,end,cost;
        cin >> start >> end >> cost;
        v.push_back({start,end,cost});
    }
    sort(v.begin(), v.end());
    
    int num = 0, total_cost = 0;
    for(auto data : v)
    {
        int s = data.start;
        int e = data.end;
        int c = data.cost;
        if(!ask(s,e))
        {
            num++;
            total_cost += c;
            U(s,e);
        }
    }
    if(num != n - 1)    total_cost = -1;
    cout << total_cost << endl;
}