Submission #2271614

---

Source Code Expand

#include <cstdio>
#include <vector>
#include <algorithm>
#include <functional>
#include <map>
#include <set>
#include <string>
#include <iostream>
#include <cassert>
#include <cmath>
using namespace std;

struct UnionFind {
        int n;
        vector<int> parent;
        vector<int> rank;
        vector<int> num;
        int find(int x) {
                if (parent[x] == x) return  x;
                return parent[x] = find(parent[x]);
        }
        UnionFind(int n_) {
                n = n_;
                parent.resize(n);
                for (int i = 0; i < n; i ++) parent[i] = i;
                rank.assign(n, 0);
                num.assign(n, 1);
        }
        void unite(int x, int y) {
                if ((x = find(x)) != (y = find(y))) {
                        if (rank[x] < rank[y]) {
                                parent[x] = y;
                                num[y] += num[x];
                        } else {
                                parent[y] = x;
                                if (rank[x] == rank[y]) rank[x] ++;
                                num[x] += num[y];
                        }
                        n --;
                }
        }
        bool same(int x, int y) { return find(x) == find(y); }
        int get() { return n; }
        int get(int x) { return num[find(x)]; }
};

int main() {
        int n, m;
        scanf("%d%d", &n, &m);
        vector<pair<int, pair<int, int>>> es;
        for (int i = 0; i < m; i ++) {
                int a, b, c;
                scanf("%d%d%d", &a, &b, &c);
                a --, b --;
                es.push_back({c, {a, b}});
        }
        sort(es.begin(), es.end());
        vector<pair<int, pair<int, int>>> use;
        UnionFind uf(n);
        long long tot = 0;
        for (int i = 0; i < (int) es.size(); i ++) {
                int a, b;
                tie(a, b) = es[i].second;
                if (uf.same(a, b)) continue;
                uf.unite(a, b);
                use.push_back(es[i]);
                tot += es[i].first;
        }
        assert((int) use.size() == n - 1);
        vector<vector<pair<int, int>>> g(n);
        for (int i = 0; i < n - 1; i ++) {
                int c = use[i].first;
                int a = use[i].second.first;
                int b = use[i].second.second;
                g[a].push_back({b, c});
                g[b].push_back({a, c});
        }
        int q;
        scanf("%d", &q);
        assert(q <= 3000);
        while (q --) {
                int s, t;
                scanf("%d%d", &s, &t);
                s --, t --;
                int maxval = 0;
                function<void (int, int, int)> dfs = [&](int u, int prev, int ma) {
                        if (u == t) {
                                maxval = ma;
                                return;
                        }
                        for (auto e : g[u]) if (e.first != prev) {
                                dfs(e.first, u, max(ma, e.second));
                        }
                };
                dfs(s, -1, 0);
                printf("%lld\n", tot - maxval);
        }
        return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:49:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d%d", &n, &m);
                              ^
./Main.cpp:53:44: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d%d%d", &a, &b, &c);
                                            ^
./Main.cpp:79:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &q);
                        ^
./Main.cpp:83:38: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
                 scanf("%d%d", &s, &t);
                                      ^

Judge Result