Алгоритм Курскала, Ошибка времени выполнения в Kattis - PullRequest
Новая
       30

Алгоритм Курскала, Ошибка времени выполнения в Kattis

3 голосов
/ 14 апреля 2019

Я пытался найти Минимальное остовное дерево на Кэттис. (https://open.kattis.com/problems/minspantree) Первый тест работает нормально, второй дает неопределенную ошибку времени выполнения. Я боролся с этим более недели. Должно быть, это какая-то логическая ошибка, но независимо от того, сколько усилий я прилагаю в это я не вижу, что не так. 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <tuple>

using namespace std;

class DisjointSet {
public:
    vector<int> parent, rank;

    DisjointSet(int _size) {
        parent.resize(_size);
        rank.resize(_size); // Maybe this?
        // make the sets
        for (int i = 0; i < _size; i++) { // fill set 
            parent[i] = i;
            rank[i] = 0;
        }
    }


    void make_set(int v) {
        parent[v] = v;
        rank[v] = 0;
    }

    int find_set(int v) {
        if (v == parent[v])
            return v;
        return parent[v] = find_set(parent[v]);
    }

    void union_sets(int a, int b) {
        a = find_set(a);
        b = find_set(b);
        if (a != b) {
            if (rank[a] < rank[b])
                swap(a, b);
            parent[b] = a;
            if (rank[a] == rank[b])
                rank[a]++;
        }
    }

};
bool sort_weight(const tuple<int, int, int> &one, const tuple<int, int, int> &two) {
    return get<2>(one) < get<2>(two); // Weight
}
bool sort_node(const tuple<int, int, int> &one, const tuple<int, int, int> &two) {
    if (get<0>(one) != get<0>(two)) {
        return get<0>(one) < get<0>(two); // node one
    } 
    return get<1>(one) < get<1>(two); // node two
}

int main()
{

    int n_nodes = 0, n_arcs = 0;
    int tmp_node1, tmp_node2, tmp_weight;

    while (cin >> n_nodes >> n_arcs) { // Until the end
        if (n_nodes == 0 && n_arcs == 0) { break; }
        if (n_arcs < n_nodes - 1) { // If it is not possible to build a MST
            cout << "Impossible\n";
        }
        else {
            int cost = 0;
            DisjointSet s(n_nodes); // make set
            vector<tuple<int, int, int>> vArcs;
            vector<tuple<int, int, int>> vResult;
            vArcs.resize(n_arcs);

            for (int i = 0; i < n_arcs; i++) {
                cin >> tmp_node1 >> tmp_node2 >> tmp_weight;
                vArcs[i] = make_tuple(tmp_node1, tmp_node2, tmp_weight);
            }


            sort(vArcs.begin(), vArcs.end(), sort_weight); // Sort by weight lowest to highest

            for (int i = 0; i < n_arcs && vResult.size()<(n_nodes - 1); i++)
            {
                if (s.find_set(get<0>(vArcs[i])) != s.find_set(get<1>(vArcs[i]))) {
                    cost += get<2>(vArcs[i]);
                    vResult.push_back(vArcs[i]);
                    s.union_sets(get<0>(vArcs[i]), get<1>(vArcs[i]));
                }
            }
            // We are done, order and print
            sort(vResult.begin(), vResult.end(), sort_node);
            cout << cost << "\n";
            for (int i = 0; i < vResult.size(); i++)
            {
                cout << get<0>(vResult[i]) << " " << get<1>(vResult[i]) << "\n";
            }
        }
    }
}

1 Ответ

0 голосов
/ 13 июня 2019

Вам необходимо прочитать весь ввод для каждого теста, даже если число ребер меньше n - 1.

...