题目描述

算法1

解答 kruscal模板题目 就是输出稍微改下
吐槽下，poj题目的样例居然是错的

C++ 代码

// poj1861.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

/*
5 8
1 2 5
1 4 2
1 5 1
2 3 6
2 4 3
3 4 5
3 5 4
4 5 6
*/

const int N = 15010;
const int M = 15010;
const int INF = 0x3f3f3f3f;

int f[N];

struct EDGE {
    int a, b, w;
}edge[M];

bool cmp(const struct EDGE& a, const struct EDGE& b) {
    return a.w < b.w;
}


int find(int x) {
    return f[x] == x ? x : f[x] = find(f[x]);
}

int n, m;

void kruscal()
{
    int maxlen = -999999;
    vector<pair<int, int>> ans;
    sort(edge, edge + m,cmp);

    for (int i = 1; i <= n; i++) f[i] = i;

    int cnt = 0;

    for (int i = 0; i < m; 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) {
            f[a] = b;
            //cout << a << b << endl;
            maxlen = max(maxlen, w);
            pair<int, int> tmp = make_pair(edge[i].a, edge[i].b);
            ans.push_back(tmp);
            cnt++;
        }
    }

    cout << maxlen << endl;
    cout << ans.size() << endl;

    for (int i = 0; i < ans.size();i++) {
        cout << ans[i].first << " " << ans[i].second << endl;
    }



    return;
}

int main()
{
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        cin >> edge[i].a >> edge[i].b >> edge[i].w;
    }

    kruscal();

    return 0;
}