let menu = ["Home", "Algorithms", "CodeHub", "VNOI Statistics"];

Overview

VOI 2013 COMNET - Mạng truyền thông

solution.md

Bài này không cần quan tâm tới điều kiện cạnh là cầu.

Sau khi đã update trọng số các cạnh, ta kiểm tra cạnh k có tiềm năng hay không như sau: Hợp nhất tất cả các cạnh có trọng số nhỏ hơn trọng số cạnh k, sau đó kiểm tra xem nếu 2 đỉnh u và v của cạnh k đã được hợp nhất thì k là cạnh không tiềm năng.

Có thể dùng disjoint set hoặc dfs/bfs.

main.cpp
Open in Github Download
#include <iostream>
#include <vector>
using namespace std;

#define LL long long

struct universe {
    vector<int> cha, rank;
    universe(int n): cha(n + 1), rank(n + 1, 0) {
        for (int i=1; i<=n; i++) cha[i] = i;
    }
    int find(int u) {
        if (cha[u] != u) cha[u] = find(cha[u]);
        return cha[u];
    }
    bool join(int u, int v) {
        u = find(u), v = find(v);
        if (u == v) return false;
        if (rank[u] == rank[v]) rank[u]++;
        if (rank[u] > rank[v]) cha[v] = u;
        else cha[u] = v;
        return true;
    }
};

struct pack { int u, v; };

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T; cin >> T;
    while (T--) {
        int n, m, Q; cin >> n >> m >> Q;
        vector<pack> e(m);
        vector<int> w(m);
        for (int i=0; i<m; i++) cin >> e[i].u >> e[i].v >> w[i];
        while (Q--) {
            int id; cin >> id; id--;
            int s; cin >> s;
            vector<int> ww(w);
            while (s--) {
                int t, w; cin >> t >> w;
                ww[t-1] = w;
            }
            universe a(n);
            for (int i=0; i<m; i++) if (ww[i] < ww[id]) {
                a.join(e[i].u, e[i].v);
            }
            if (a.join(e[id].u, e[id].v)) cout << "NO\n";
            else cout << "YES\n";
        }
    }
    return 0;
}
test.py
Open in Github Download
# Code sinh test
import random
T = 1
print(T)
for i in range(T):
    n = 100000
    m = 1000000
    Q = 30
    print(n, m, Q)
    for j in range(m):
        x, y = random.sample(range(n), 2)
        w = random.randrange(1000000000) + 1
        print(x+1, y+1, w)
    for j in range(Q):
        k = 100
        print(random.randrange(m) + 1, k, end=' ')
        l = random.sample(range(m), k)
        for x in l:
            print(x+1, random.randrange(1000000000)+1, end=' ')
        print('')
Comments