poj3714突袭的代码实现

以下是 poj3714 突袭的代码实现，使用了 Kruskal 算法求解最小生成树：

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

const int MAXN = 20005;
const int MAXM = 100005;

struct Edge {
    int u, v, w;
    bool operator<(const Edge& other) const {
        return w < other.w;
    }
};

int n, m, p;
int parent[MAXN], depth[MAXN];
Edge edges[MAXM];

void make_set(int v) {
    parent[v] = v;
    depth[v] = 0;
}

int find_set(int v) {
    if (v == parent[v]) {
        return v;
    }
    return parent[v] = find_set(parent[v]);
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (depth[a] < depth[b]) {
            swap(a, b);
        }
        parent[b] = a;
        if (depth[a] == depth[b]) {
            depth[a]++;
        }
    }
}

int kruskal() {
    int ans = 0;
    for (int i = 1; i <= n; i++) {
        make_set(i);
    }
    sort(edges, edges + m);
    for (int i = 0; i < m; i++) {
        int u = edges[i].u, v = edges[i].v, w = edges[i].w;
        if (find_set(u) != find_set(v)) {
            union_sets(u, v);
            ans += w;
        }
    }
    return ans;
}

int main() {
    while (cin >> n >> m >> p) {
        for (int i = 0; i < m; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            edges[i] = {u, v, w};
        }
        int ans1 = kruskal();
        for (int i = 1; i <= n; i++) {
            make_set(i);
        }
        for (int i = 0; i < p; i++) {
            int u, v, w;
            cin >> u >> v >> w;
            edges[i] = {u, v, -w};
        }
        int ans2 = kruskal();
        cout << ans2 - ans1 << endl;
    }
    return 0;
}

在这个实现中，使用了一个 `Edge` 结构体来表示一条边，包括起点、终点和边权。然后使用 Kruskal 算法求解最小生成树，分别计算突袭前和突袭后的最小生成树的权值和，最终答案为突袭后的权值和减去突袭前的权值和。