QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#588113#415. 最小生成树shiqiaqiayaCompile Error//C++174.0kb2024-09-25 01:34:132024-09-25 01:34:14

Judging History

你现在查看的是最新测评结果

  • [2024-09-25 01:34:14]
  • 评测
  • [2024-09-25 01:34:13]
  • 提交

answer

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/priority_queue.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define int long long
using ll = long long;
mt19937_64 rd(time(0));
template <class K, class C = less<>> using paring_heap = __gnu_pbds::priority_queue<K, C>;
template <class K, class V = null_type, class C = less<>> using rb_tree = tree<K, V, C, rb_tree_tag, tree_order_statistics_node_update>;
template <class T, class ... A> void debug(const T & t, const A & ... a) { cerr << "[" << t, ((cerr << ", " << a), ...), cerr << "]\n"; }
const ll mod = [](bool n) { return n ? 998244353 : 1e9 + 7; } (1);

template <ll mod = mod> ll binpow(ll a, ll b, ll res = 1) {
    for (a %= mod; b; b >>= 1, (a *= a) %= mod) {
        if (b & 1) (res *= a) %= mod;
    }
    return res;
}

vector<signed> inv, fact, invfa;
auto INIT_FACT = ([](int n) {
    inv = fact = invfa = vector<signed>(n + 1, 1);
    for (int i = 2; i <= n; i++) {
        fact[i] = (ll)fact[i - 1] * i % mod, invfa[i] = (ll)invfa[i - 1] * (inv[i] = (mod - mod / i) * inv[mod % i] % mod);
    }
} (0), true);
ll C(int n, int m) { return min(n - m, m) < 0 ? 0 : (ll)fact[n] * invfa[m] % mod * invfa[n - m] % mod; }
ll P(int n, int m) { return min(n - m, m) < 0 ? 0 : (ll)fact[n] * invfa[n - m] % mod; }
ll LC(ll n, ll m) { return !m ? 1 : C(n % mod, m % mod) * LC(n / mod, m / mod) % mod; }

// vector<int> dfn, dcc, is_bridge;
// vector dc(0, vector<int>());

// [&](int n, int m, int tot_dfn = 0) {
//     vector<int> low(n + 1); // 邻接表要记录编号
//     dfn = dcc = vector<int>(n + 1), is_bridge = vector<int>(m + 1); 

//     for (int root = 1; root <= n; root++) {
//         stack<int> s;
//         auto Tarjan = [&](auto && Tarjan, int u, int from_edge) -> void {
//             s.push(u); dfn[u] = low[u] = ++tot_dfn;
//             for (auto & i : adj[u]) {
//                 int v = e[i][0] ^ e[i][1] ^ u;
//                 if (!dfn[v]) {
//                     Tarjan(Tarjan, v, i);
//                     low[u] = min(low[u], low[v]);
//                     if (low[v] > dfn[u]) {
//                         is_bridge[i] = true;
//                     }
//                 } else if (i != from_edge) {	//用from_edge而不用father是因为可能重边
//                     low[u] = min(low[u], dfn[v]);
//                 }
//             }
//             if (dfn[u] == low[u]) {
//                 vector<int> tmp;
//                 while (!tmp.size() || tmp.back() != u) {
//                     int v = s.top(); s.pop();
//                     dcc[v] = dc.size(), tmp.push_back(v);
//                 }
//                 dc.push_back(tmp);
//             }
//         };
//         if (!dfn[root]) {
//             Tarjan(Tarjan, root, -1);
//         }
//     }
// } ();

// struct Tarjan_UnDir :  {
    
// };

struct DSU : vector<signed> {
    DSU(int n) : vector(n) { iota(begin(), end(), 0); }
    int find(int u) { return at(u) == u ? u : at(u) = find(at(u)); }
    int merge(int u, int v) { return find(u) == find(v) ? -1 : at(find(u)) = find(v); }
};

template <int len = 3> struct Kruskal : vector<array<int, len>> {    // {w, u, v}
    using e = vector<array<int, len>>;
    DSU dsu;
    int sum = 0;
    e res = {};
    Kruskal(int n, int m) : e(m), dsu(n) {}
    template <class C = less<>> void operator()(C && cmp = C()) {
        sort(e::begin(), e::end(), cmp);
        for (auto & x : *this) {
            if (dsu.merge(x[1], x[2]) != -1) sum += w, res.emplace_back(x);
        }
    }
};

void QAQ() {
    int n, m;
    cin >> n >> m;

    Kruskal e(n + 1, m);

    for (int i = 0; i < m; i++) {
        cin >> e[i][1] >> e[i][2] >> e[i][0];
    }
    e([&](auto & x, auto & y) { return x[0] < y[0]; });
    cout << e.sum << "\n";
}

signed main() {
    cin.tie(0) -> sync_with_stdio(0);
    int t = 1;
    // cin >> t;
    for (cout << fixed << setprecision(12); t--; QAQ());
}

详细

answer.code: In member function ‘void Kruskal<len>::operator()(C&&)’:
answer.code:91:53: error: ‘w’ was not declared in this scope
   91 |             if (dsu.merge(x[1], x[2]) != -1) sum += w, res.emplace_back(x);
      |                                                     ^