【最小生成树】Battle Over Cities - Hard Version (35)

缺乏、安全感 2022-06-04 00:19 129阅读 0赞

Think:  
1知识点：最小生成树  
2题意：  
（１）：输入含有n(n<=500)个结点的连通图，询问最重要的点，最重要点的定义为删掉这个点及其所连的边，需要最多花费修复已经不再使用的边使得剩下的结点继续保持连通  
（2）：最重要的点可能有多个  
3思路：  
（1）：记录所有边的信息，初始存在的边可置连接权值为0，遍历每一个点(假设删除当前遍历点及其所连的边，然后将其他n-1个点通过最小生成树算法连成连通图，记录花费)  
4反思：  
（1）：最重要的点可能有多个  
（2）：删除一点之后可能之后的图不连通  
（3）：最重要的点输出顺序为按照字典序  
（4）：n == 1的情况需要特殊判断

以下为Accepted代码——Kruskal算法

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    
    struct Edge{
        int u, v, w;
        bool operator < (const Edge &b) const{
            return w < b.w;
        }
    }edge[404014];
    
    struct Node{
        int id, sum_w;
        bool operator < (const Node &b) const{
            if(sum_w == b.sum_w) return id < b.id;
            return sum_w > b.sum_w;
        }
    }rec[504];
    
    int n, m;
    int f[504];
    
    void init_f();
    int get_f(int x);
    bool Merge(int x, int y);
    int Kruskal(int id);
    
    int main(){
        int sa;
        while(~scanf("%d %d", &n, &m)){
            if(n == 1){
                printf("0\n");
            }
            for(int i = 0; i < m; i++){
                scanf("%d %d %d %d", &edge[i].u, &edge[i].v, &edge[i].w, &sa);
                if(sa) edge[i].w = 0;
            }
            sort(edge, edge+m);
            for(int i = 1; i <= n; i++){
                rec[i].id = i;
                rec[i].sum_w = Kruskal(i);
            }
            sort(rec+1, rec+n+1);
            int mav = rec[1].sum_w;
            if(mav == 0){
                printf("0\n");
            }
            else {
                printf("%d", rec[1].id);
                for(int i = 2; i <= n; i++){
                    if(rec[i].sum_w == mav){
                        printf(" %d", rec[i].id);
                    }
                    else break;
                }
                printf("\n");
            }
        }
        return 0;
    }
    void init_f(){
        for(int i = 0; i <= n; i++)
            f[i] = i;
        return;
    }
    int get_f(int x){
        if(x == f[x]) return x;
        return f[x] = get_f(f[x]);
    }
    bool Merge(int x, int y){
        int t1 = get_f(x);
        int t2 = get_f(y);
        if(t1 == t2) return false;
        else {
            f[t2] = t1;
            return true;
        }
    }
    int Kruskal(int id){
        int num = 0, sum = 0;
        init_f();
        for(int i = 0; i < m; i++){
            if(edge[i].u == id || edge[i].v == id)
                continue;
            if(Merge(edge[i].u, edge[i].v)){
                num++;
                sum += edge[i].w;
            }
            if(num == n-2) break;
        }
        if(num == n-2) return sum;
        else return inf;
    }