1001 Battle Over Cities - Hard Version (35分)

题目传送门：1001 Battle Over Cities - Hard Version (35分)

一、题目大意

被敌人占领的城市，与这个城市所有相邻的边都无法通行。如果某一点被占领后需要将剩余的点相连花费的代价最大，则这点为重点关注的点。如果产生最大代价有多个相同的点，则都要输出。

二、解题思路

去掉一个点后，生成的最小生成树的权重最大的情况。
注意去掉一个点后可能是不连通的图。
打擂台法+Prim算法求最小生成树的权和。
可以假设完好的边长为0，只需要修可以修的边。

三、AC代码

#include<bits/stdc++.h>
using namespace std;
const int N = 501, MAX = 9999999;
int a[N][N];
int vis[N], T[N], dis[N];
int n, m,maximum = 0;
int Prim(int x){// x为去掉的点
    int source = 1;
    if(x == 1){
        source = 2;
    }
    int res = 0;
    fill(vis+1, vis+n+1, 0);
    for(int i = 1; i <= n; i++){
        dis[i] = a[source][i];
    }
    dis[x] = 0;
    vis[source] = 1;
    for(int i = 1; i < n-1; i++){
        int u = -1, d = MAX;
        for(int j = 1; j <= n; j++){
            if(j == x)continue;
            if(vis[j] == 0 and dis[j] <= d){
                d = dis[j];
                u = j;
            }
        }
        if(u == -1)return MAX;
        vis[u] = 1;
        for(int j = 1; j <= n; j++){
            if(j == x)continue;
            if(vis[j] == 0 and dis[j] > a[u][j])dis[j] = a[u][j];
        }
    }

    for(int i = 1; i <= n; i++){
        if(dis[i] == MAX)return MAX;
        res += dis[i];
    }
    return res;
}
int main(){
    cin >> n >> m;
    int u, v, cost, status;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            a[i][j] = a[j][i] = MAX;
        }
    }
    for(int i = 1; i <= n; i++){
        a[i][i] = 0;
    }
    for(int i = 0; i < m; i++){
        cin >> u >> v >> cost >> status;
        if(status)
            a[u][v] = a[v][u] = 0;
        else
        {
            a[u][v] = a[v][u] = cost;
        }
    }
    for(int i = 1; i <= n; i++){
        // 去掉点i，然后求最小生成树，Prim
        T[i] = Prim(i);
        maximum = max(maximum, T[i]);
    }
    bool flag = false;
    if(maximum == 0){
        cout << 0 << endl;
        return 0;
    }
    for(int i = 1; i <= n; i++){
        if(T[i] == maximum){
            if(flag){
                cout << ' ' << i;
            }else{
                flag = true;
                cout << i;
            }
        }
    }
    if(flag){
        cout << endl;
    }else{
        cout << 0 << endl;
    }
}

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
  
43
  
44
  
45
  
46
  
47
  
48
  
49
  
50
  
51
  
52
  
53
  
54
  
55
  
56
  
57
  
58
  
59
  
60
  
61
  
62
  
63
  
64
  
65
  
66
  
67
  
68
  
69
  
70
  
71
  
72
  
73
  
74
  
75
  
76
  
77
  
78
  
79
  
80
  
81
  
82
  
83
  
84
  
85
  
86
  
87
 

文章来源: blog.csdn.net，作者：爱玲姐姐，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/jal517486222/article/details/104329691