PAT「1001 Battle Over Cities - Hard Version (35分)」

1. 题目

题目链接：PAT「1001 Battle Over Cities - Hard Version (35分)」 。

Description

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$ ($\leq 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

2. 题解

分析

直接暴力枚举，考虑去除每个节点后，对剩余的节点使用 Prim 算法计算生成最小生成树所需要的代价，如果不能生成最小生成树，则代价为无穷 INF；依据题意可知，只有 destroyed 的高速公路需要修复代价，即 Status = 0；而 Status = 1 的高速公路不需要修复代价，即修复代价为 $0$ 。由于 Status = 1 的高速公路修复代价都一样，故对这部分高速公路可以直接使用并查集+数组来合并可以合并的联通集；对于 Status = 0 的高速公路的部分，在前者操作的基础上，使用有序数组（按照 cost 从高到底降序）来进一步生成最小生成树，即并查集+有序数组。由于去除了 Status = 1，故进行 sort 操作较快。

由于 $N \leq 500$，故 $M \leq N*(N-1)/2 = 124750$，边 sort 复杂度 $O(M\log(M))$，答案 sort 复杂度 $O(N\log(N))$，枚举所有节点并构建最小生成树 $O(NM)$。故最终复杂度为 $O(NM)$。由于数据不是很大，故「直接枚举+并查集+Prim」算法也跑的挺快的。

代码

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 505, MAXM = 130000;
const int INF = 0x7fff0000;

//边
typedef struct {
    int u, v;       // u、v 分别为该边的两个端点
}edge;

//点
typedef struct {
    int i, cost;    // i 为节点，cost 为去点该节点需要的最小花费 
}ans;

int num_edge;
int father[MAXN], graph[MAXN][MAXN];

bool operator < (const edge e1, const edge e2) {
    return graph[e1.u][e1.v] < graph[e2.u][e2.v];
}

bool operator < (const ans a1, const ans a2) {
    return a1.cost == a2.cost ? a1.i < a2.i : a1.cost > a2.cost;
}

int len_vq;
int len_vpqe;
int len_vpqa;
edge vq[MAXM];
edge vpqe[MAXM];
ans vpqa[MAXN];

// 初始化
void init(int n) {
    num_edge = n-2;
    for(int i = n; i; --i) {
        father[i] = i;
    }
}

// 寻找并查集的根节点
int findfather(int x) {
    return x == father[x] ? x : (father[x] = findfather(father[x]));
}

// 根据已有边尽可能合并节点
void build(int x) {
    for(int i = 0; i < len_vq && num_edge; ++i) {
        if(vq[i].u != x && vq[i].v != x) {
            if(findfather(vq[i].u) != findfather(vq[i].v)) {
                father[father[vq[i].v]] = father[vq[i].u];
                --num_edge;
            }
        }
    }
}

// 根据可修复边合并所有并查集得到最小生成树
int repair(int x) {
    int res = 0;
    for(int i = 0; i < len_vpqe && num_edge; ++i) {
        if(vpqe[i].u != x && vpqe[i].v != x) {
            if(findfather(vpqe[i].u) != findfather(vpqe[i].v)) {
                father[father[vpqe[i].v]] = father[vpqe[i].u];
                --num_edge;
                res += graph[vpqe[i].u][vpqe[i].v];
            }
        }
    }
    if(num_edge) {
        res = INF;
    }
    return res;
}

int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = m; i; --i) {
        int x, y, cost, flag;
        scanf("%d%d%d%d", &x, &y, &cost, &flag);
        graph[x][y] = cost;
        if(flag) {
            vq[len_vq++] = edge{x,y};
        } else {
            vpqe[len_vpqe++] = edge{x,y};
        }
    }
    sort(vpqe, vpqe+len_vpqe);
    for(int i = n; i; --i) {
        init(n);
        build(i);
        int res = repair(i);
        vpqa[len_vpqa++] = ans{i, res};
    }
    sort(vpqa, vpqa+len_vpqa);
    if(vpqa[0].cost == 0) {
        printf("0\n");
    } else {
        printf("%d", vpqa[0].i);
        for(int i = 1; i < len_vpqa && vpqa[i].cost == vpqa[0].cost; ++i) {
            printf(" %d", vpqa[i].i);
        }
        printf("\n");
    }
    return 0;
}