题目

原题链接
{% fold 点击显/隐题目 %}

It is vitally important to have all the cities connected by highways in a war. If a city is conquered by the enemy, all the highways from/toward that city will be closed. To keep the rest of the cities connected, we must repair some highways with the minimum cost. On the other hand, if losing a city will cost us too much to rebuild the connection, we must pay more attention to that city.

Given the map of cities which have all the destroyed and remaining highways marked, you are supposed to point out the city to which we must pay the most attention.

Input Specification:
Each input file contains one test case. Each case starts with a line containing 2 numbers N (<=500), and M, which are the total number of cities, and the number of highways, respectively. Then M lines follow, each describes a highway by 4 integers:

City1 City2 Cost Status
where City1 and City2 are the numbers of the cities the highway connects (the cities are numbered from 1 to N), Cost is the effort taken to repair that highway if necessary, and Status is either 0, meaning that highway is destroyed, or 1, meaning that highway is in use.

Note: It is guaranteed that the whole country was connected before the war.

Output Specification:
For each test case, just print in a line the city we must protest the most, that is, it will take us the maximum effort to rebuild the
connection if that city is conquered by the enemy.

In case there is more than one city to be printed, output them in increasing order of the city numbers, separated by one space, but no
extra space at the end of the line. In case there is no need to repair any highway at all, simply output 0.

Sample Input 1:
4 5
1 2 1 1
1 3 1 1
2 3 1 0
2 4 1 1
3 4 1 0

Sample Output 1:
1 2

Sample Input 2:
4 5
1 2 1 1
1 3 1 1
2 3 1 0
2 4 1 1
3 4 2 1

Sample Output 2:
0

解析

题意为：找出删去该节点后，最小生成树花费最大的节点集合。
需要注意：如果删去某些节点后，无法生成最小生成树，那么该节点的花费为无穷大

按照Kruskal的算法来说，应该每次计算最小生成树前，需要对所有边的权值进行排序。
但是如果这样会超时（时限只有800ms）
可以发现，如果一条高速公路本来就是完好的，那么其花费永远是0（如果两端的城市没有被占领）
而对于两端被占领的公路，在Kruskal里其实应该直接忽略掉（因为端点不需要连入最小生成树）
因此，所有正常的公路，权值都为0；损坏的公路权值为其花费。
这样只需要排序一次即可，不需要根据被占领的城市来重新排序（权值被改变的公路已经不需要考虑，直接跳过即可）。

算法用到了：Kruskal+ufs
Kruskal是一种最小生成树算法，思路为：将所有边按照权值排序。
从小到大检查两个端点的连通分量的根值。
如果两个根值相同，说明他们在一个连通分量，不需要连接。
如果两个根值不同，说明他们不在一个连通分量，需要将当前边插入（因为是从小到大，根据贪心的思路，应该选取当前边）。然后更新其中一个连通分量的根值为另一个连通分量的根值。
ufs则是带有路径压缩的查询连通分量根值的一种方法，每次查询的同时，可以将连通分量树的层数尽可能减少。

这道题时限过小，在最坏情况下，时间复杂度为\(O(n^3)\)，似乎不太应该能通过

代码

C++解法

{% fold 点击显/隐代码 %}

#include <algorithm>
#include <cstdio>
using namespace std;

#define Log(format, ...) // printf(format, ##__VA_ARGS__)

struct Node {
    int u, v, w;
    Node(int _u = 0, int _v = 0, int _w = 0) : u(_u), v(_v), w(_w) {}
    bool operator<(const Node &rhs) const { return w < rhs.w; }
};

const int maxn = 505;
int ans[maxn];
Node edge[maxn * maxn];
int edgePos;

void addEdge(Node e) {
    edge[edgePos++] = e;
    Log("addEdge %d -> %d cost %d\n", e.u, e.v, e.w);
}

int f[maxn];
int ufs(int x) { return f[x] == x ? x : f[x] = ufs(f[x]); }
int Kruskal(int n, int m, int d) {
    int cost = 0;
    for (int i = 0; i <= n; ++i)
        f[i] = i;

    for (int i = 0; i < m; ++i) {
        int u = edge[i].u, v = edge[i].v;
        int x = ufs(u), y = ufs(v);
        Log("\t\t%d(%d) %d(%d)\n", u, x, v, y);
        if (u != d && v != d && x != y) { //　不连接被占领的城市
            Log("\t\tconnect %d -> %d cost %d\n", u, v, edge[i].w);
            f[x] = y;
            cost += edge[i].w;
        }
    }
    int root = 1 == d ? ufs(2) : ufs(1);
    for (int i = 1; i <= n; ++i) {
        if (i != d && ufs(i) != root)
            cost = -1; // 无法连通
    }
    return cost;
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    edgePos = 0;
    for (int i = 0; i < m; ++i) {
        int u, v, w, s;
        scanf("%d%d%d%d", &u, &v, &w, &s);
        addEdge(Node(u, v, s ? 0 : w));
    }
    sort(edge, edge + m);

    int ansPos = 0, maxCost = 0;
    for (int i = 1; i <= n; ++i) {
        int cost = Kruskal(n, m, i);
        Log("Test %d cost %d\n", i, cost);
        if (maxCost != -1 && (cost > maxCost || cost == -1)) {
            maxCost = cost;
            ansPos = 0;
            ans[ansPos++] = i;
            Log("\tmax value update.\n");
        } else if (cost == maxCost) {
            ans[ansPos++] = i;
            Log("\tadd to ans.\n");
        }
    }

    if (maxCost == 0) {
        printf("0");
    } else {
        for (int i = 0; i < ansPos; ++i) {
            if (i)
                printf(" ");
            printf("%d", ans[i]);
        }
    }
    printf("\n");

    return 0;
}

{% endfold %}