PAT顶级 || 1001 Battle Over Cities

1001 Battle Over Cities - Hard Version (35分)

思路：最小生成树MST

• Kruskal算法：取不形成环的最短边的集合。
  不形成环这点用并查集来保证。

• in use的边权值直接看成0，destroyed的边权值为cost，边全部输入完后排序一次。

• 删去一个点和与之相连的边，求剩下的点的MST，找删去后MST总边权最大的点。

• ⚠️删去某点后不存在MST的情况

#include <cstdio>
#include <algorithm>
#include <vector>

#define INF 0x3fffffff
using namespace std;

// kruskal MST
struct Road {
    int cost, v1, v2;

    bool operator<(const Road &r2) const {
        if (cost != r2.cost) return cost < r2.cost;
        return make_pair(v1, v2) < make_pair(r2.v1, r2.v2);
    }
};

int nn, mm;
int graph[501][501], uf[501];

int find_(int sn) {
    return uf[sn] < 0 ? sn : uf[sn] = find_(uf[sn]);
}

void union_(int a, int b) {
    a = find_(a);
    b = find_(b);
    int M = max(a, b), m = min(a, b);
    if (M != m) {
        uf[m] += uf[M];
        uf[M] = m;
    }
}

vector<int> res;
vector <Road> edges;
int mmax = -1;

void MST(int del_v) {
    fill(uf, uf + 501, -1);
    int ind = 0, cnt = 0, total = 0;
    for (; ind < mm && cnt < nn - 2; ind++) {
        if (edges[ind].v1 != del_v && edges[ind].v2 != del_v) {
            int v1 = edges[ind].v1, v2 = edges[ind].v2;
            if (find_(v1) != find_(v2)) {
                union_(v1, v2);
                total += edges[ind].cost;
                cnt++;
            }
        }
    }
    if (cnt == nn - 2) {
        if (total == mmax) res.emplace_back(del_v);
        else if (total > mmax) {
            mmax = total;
            res.clear();
            res.emplace_back(del_v);
        }
    } else {
        if (mmax != INF) {
            res.clear();
            mmax = INF;
        }
        res.emplace_back(del_v);
    }
}

int main() {
    scanf("%d%d", &nn, &mm);
    for (int i = 0; i < mm; ++i) {
        int v1, v2, cost, st;
        scanf("%d%d%d%d", &v1, &v2, &cost, &st);
        if (st) cost = 0;
        edges.emplace_back(Road{cost, min(v1, v2), max(v1, v2)});
    }
    sort(edges.begin(), edges.end());
    for (int i = 1; i <= nn; i++) {
        MST(i);
    }
    if (mmax) {
        int i = 0;
        for (; i < res.size() - 1; i++) printf("%d ", res[i]);
        printf("%d\n", res[i]);
    } else puts("0");
    return 0;
}