只输出yes?
查看原帖
只输出yes?
1108078
nothing_exe_studio楼主2024/5/9 20:07

code

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> parent, rk;

int find(int x) {
    if (parent[x] != x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

void unionSets(int x, int y) {
    int rootX = find(x);
    int rootY = find(y);
    if (rootX == rootY) {
        return;
    }
    if (rk[rootX] < rk[rootY]) {
        parent[rootX] = rootY;
    } else if (rk[rootX] > rk[rootY]) {
        parent[rootY] = rootX;
    } else {
        parent[rootY] = rootX;
        rk[rootX]++;
    }
}

struct Edge {
    int u, v, w;
};

int main() {
    int n, m, q;
    cin >> n >> m >> q;

    vector<Edge> edges(m);
    for (int i = 0; i < m; ++i) {
        cin >> edges[i].u >> edges[i].v >> edges[i].w;
    }

    sort(edges.begin(), edges.end(), [](const Edge& a, const Edge& b) {
        return a.w < b.w;
    });

    parent.resize(n + 1);
    rk.resize(n + 1);
    for (int i = 1; i <= n; ++i) {
        parent[i] = i;
        rk[i] = 0;
    }

    vector<string> answers(q);

    for (int i = 0; i < q; ++i) {
        int u, v, w;
        cin >> u >> v >> w;

        int rootU = find(u);
        int rootV = find(v);

        bool found = false;

        for (const auto& edge : edges) {
            if (edge.w == w) {
                if ((find(edge.u) == rootU && find(edge.v) == rootV) || (find(edge.u) == rootV && find(edge.v) == rootU)) {
                    found = true;
                    break;
                }
            } else if (edge.w > w) {
                break;
            }
        }

        if (found) {
            answers[i] = "No";
        } else {
            unionSets(u, v);
            answers[i] = "Yes";
        }
    }

    for (const auto& answer : answers) {
        cout << answer << endl;
    }

    return 0;
}

2024/5/9 20:07
加载中...