p462.ans1
======================
5
2 3 1 4

=================
p462.cpp
======================
#include <bits/stdc++.h>
// #include <coding_library/graph/dsu.hpp>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

class DSU {
  public:
    int n;
    vector<int> par;
    vector<int> sz;

    DSU(int _n = 0) { init(_n); }

    void init(int _n) {
        n = _n;
        par.assign(n + 1, 0);
        sz.assign(n + 1, 0);
        for(int i = 0; i <= n; i++) {
            par[i] = i;
            sz[i] = 1;
        }
    }

    int root(int u) { return par[u] = ((u == par[u]) ? u : root(par[u])); }
    bool connected(int x, int y) { return root(x) == root(y); }

    int unite(int x, int y) {
        x = root(x), y = root(y);
        if(x == y) {
            return x;
        }
        if(sz[x] > sz[y]) {
            swap(x, y);
        }
        par[x] = y;
        sz[y] += sz[x];
        return y;
    }

    vector<vector<int>> components() {
        vector<vector<int>> comp(n + 1);
        for(int i = 0; i <= n; i++) {
            comp[root(i)].push_back(i);
        }
        return comp;
    }
};

int n;
vector<tuple<int, int, int, int>> wires;

void read() {
    vector<int> nodes;

    cin >> n;
    wires.resize(n);
    for(auto& [u, v, r, p]: wires) {
        cin >> u >> v >> r >> p;
        nodes.push_back(u);
        nodes.push_back(v);
    }

    sort(nodes.begin(), nodes.end());
    nodes.erase(unique(nodes.begin(), nodes.end()), nodes.end());

    for(auto& [u, v, r, p]: wires) {
        u = lower_bound(nodes.begin(), nodes.end(), u) - nodes.begin();
        v = lower_bound(nodes.begin(), nodes.end(), v) - nodes.begin();
    }
}

void solve() {
    // We can notice that we always will maintain an MST based on the
    // reliability. This means that no matter what order we choose the MST will
    // be almost the same (we can get convinced by correctness of Kruskal) - the
    // only difference comes in how we order the edges of the same reliability.
    // This is also not as hard - we simply want to keep the most expensive ones
    // last (so that previous cheaper wires get deleted). In other words it's
    // enough to sort the wires by "r" first, and then break ties by "p". This
    // is the order we will do and we could simulate the process with some
    // advanced data structures like link-cut trees, but there is an easier way
    // to recover the final configuration and price - we can simply do Kruskal
    // from the back.

    DSU dsu(2 * n);

    vector<int> perm(n);
    iota(perm.begin(), perm.end(), 0);

    sort(perm.begin(), perm.end(), [&](int i, int j) {
        auto& [u1, v1, r1, p1] = wires[i];
        auto& [u2, v2, r2, p2] = wires[j];
        if(r1 != r2) {
            return r1 < r2;
        }
        return p1 < p2;
    });

    int64_t total_cost = 0;
    for(int i = n - 1; i >= 0; i--) {
        int idx = perm[i];
        auto& [u, v, r, p] = wires[idx];
        if(!dsu.connected(u, v)) {
            dsu.unite(u, v);
            total_cost += p;
        }
    }

    cout << total_cost << "\n";
    for(int i = 0; i < n; i++) {
        if(i > 0) {
            cout << " ";
        }
        cout << perm[i] + 1;
    }
    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    // cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        // cout << "Case #" << test << ": ";
        solve();
    }

    return 0;
}

=================
p462.in1
======================
4
10 20 5 3
20 11 5 2
10 11 7 1
1 2 1 1

=================
statement.txt
======================
462. Electrician
Time limit per test: 0.25 second(s)
Memory limit: 65536 kilobytes
input: standard
output: standard



An electrician Vasya has got an assignment to solder n wires. His boss specified the requirements precisely, so for each wire Vasya knows exactly where its endpoints should be soldered to. Two identifiers ai,bi are given for each wire, meaning that one endpoint of the wire should be soldered to the place ai, and the other endpoint should be soldered to the place bi. It doesn't matter which endpoint will be soldered to which place. Also each wire has two more characteristics ri and pi, where ri is its reliability and pi is its cost.

The only way for Vasya to express himself in such a rigorous constraints is to choose an order, and solder all wires in this order, one after another. As an experienced electrician Vasya knows what a short circuit is — it occurs when a scheme contains a cycle, in other words when there is more than one simple path over wires from one place to another. So, if a short circuit occurs after a wire is soldered, the least reliable wire in the cycle burns out (you may think that the least reliable wire disappears from the scheme). If there are several least reliable wires in the cycle, the one of them which was soldered earlier burns out. It is clear that after a wire burns out, the scheme doesn't have any cycles.

When Vasya is done with soldering, he ends up with a scheme of soldered wires. So, he wants to solder all wires in such an order, that the total cost of wires in a resulting scheme will be as maximal as possible.

Input
The first line of input contains a single integer n (1 ≤ n ≤ 30000). Each of the following n lines contains four integer numbers ai,bi,ri,pi (1 ≤ ai,bi, ri,pi ≤ 109; ai ≠q bi), where ai and bi are identifiers of the places for endpoints of i-th wire, ri is the reliability of the wire, and pi is the cost of the wire. There can be more than one wire between any pair of places.

Output
Print the required maximal total cost to the first line of output. Print the order of wires for soldering to the second line, delimiting wire indices with a single space.

You may print any solution if there are many of them.

Example(s)
sample input
sample output
4
10 20 5 3
20 11 5 2
10 11 7 1
1 2 1 1
5
2 3 1 4 



Note
In the sample test Vasya can choose any order with the only rule: the second wire should be soldered before the first one. If he violates the rule, the total cost will be 4 instead of 5.



=================
