H - Highways——最小生成树Kruskal算法+Prim算法

水深无声 2022-06-11 07:18 189阅读 0赞

Think:  
1知识点：最小生成树Kruskal算法+Prim算法  
2思考：  
1>多组输入超时，单组输入AC——why???  
2>排序时结构体内重载小于号快于再单独写cmp判断函数  
3题意：需要使得n个结点构成连通图，已知有m个结点已经连接，询问最小花费构成连通图还需要连接那些结点  
4思路：  
1>Kruskal算法：先预处理所有结点距离，预处理结点距离时将其入队，之后按照权值排序，然后在通过并查集将已经连接的结点连成集合，记录有效边，进而按照已经排序的顺序更新试探，直到连接n个结点  
2>Prim算法：先预处理所有结点距离，构造二维地图，然后通过已经连接的结点更新地图(可将地图中已经连接的结点预处理边权为0)，进而Prim算法即可

[vjudge题目链接][vjudge]

以下为Accepted代码——Prim算法-79ms

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    
    struct Node{
        int x, y;
    }node[1014];
    
    struct Dist{
        int u;
        int w;
    }dis[1014];
    
    int vis[1014], e[1014][1014];
    
    void Prim(int n);
    int Dis(int u, int v);
    
    int main(){
        int n, m, i, j, u, v;
        scanf("%d", &n);
        for(i = 1; i <= n; i++)
            scanf("%d %d", &node[i].x, &node[i].y);
        for(i = 1; i <= n; i++){
            for(j = i+1; j <= n; j++){
                e[i][j] = e[j][i] = Dis(i, j);
            }
        }
        scanf("%d", &m);
        while(m--){
            scanf("%d %d", &u, &v);
            e[u][v] = e[v][u] = 0;
        }
        Prim(n);
        return 0;
    }
    int Dis(int u, int v){
        int dx = node[u].x - node[v].x;
        int dy = node[u].y - node[v].y;
        int dl = dx*dx + dy*dy;
        return dl;
    }
    void Prim(int n){
        int i, miv, v, num;
        memset(vis, 0, sizeof(vis));
        for(i = 1; i <= n; i++){
            dis[i].w = e[1][i];
            dis[i].u = 1;
        }
        vis[1] = 1, dis[1].w = 0, num = 1;
        while(num < n){
            miv = inf;
            for(i = 1; i <= n; i++){
                if(!vis[i] && dis[i].w < miv){
                    miv = dis[i].w, v = i;
                }
            }
            vis[v] = 1, num++;
            if(e[v][dis[v].u])
                printf("%d %d\n", dis[v].u, v);
            for(i = 1; i <= n; i++){
                if(!vis[i] && e[v][i] < dis[i].w){
                    dis[i].w = e[v][i];
                    dis[i].u = v;
                }
            }
        }
    }

以下为Time Limit Exceeded代码——Kruskal算法-排序：单独写cmp判断函数

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    
    using namespace std;
    
    const double zero = 1e-4;
    
    struct Edge{
        int u;
        int v;
        int w;
    }edge[501400];
    
    struct Node{
        int x;
        int y;
    }node[1014];
    
    bool cmp(struct Edge a, struct Edge b){
        return a.w < b.w;
    }
    
    int tp, f[1014];
    
    void Init(int n);
    int get_f(int v);
    bool Merge(int u, int v);
    double Dis(int i, int j);
    
    int main(){
        int n, m, i, j, t, num, u, v;
        scanf("%d", &n);
            Init(n);
            for(i = 1; i <= n; i++){
                scanf("%d %d", &node[i].x, &node[i].y);
            }
            t = 0;
            for(i = 1; i <= n; i++){
                for(j = i+1; j <= n; j++){
                    edge[t].u = i, edge[t].v = j;
                    edge[t].w = Dis(i, j);
                    t++;
                }
            }
    
            sort(edge, edge+t, cmp);
    
            num = 0;
            scanf("%d", &m);
            while(m--){
                scanf("%d %d", &u, &v);
                if(Merge(u, v))
                    num++;
            }
            for(i = 0; i < t; i++){
                u = edge[i].u, v = edge[i].v;
                if(Merge(u, v)){
                    printf("%d %d\n", u, v);
                    num++;
                }
                if(num == n-1)
                    break;
            }
    
        return 0;
    }
    void Init(int n){
        for(int i = 1; i <= n; i++)
            f[i] = i;
    }
    double Dis(int i, int j){
        int dx = node[i].x - node[j].x;
        int dy = node[i].y - node[j].y;
        int xy = dx*dx + dy*dy;
        return xy;
    }
    bool Merge(int u, int v){
        int t1 = get_f(u);
        int t2 = get_f(v);
        if(t1 != t2){
            f[t2] = t1;
            return true;
        }
        else
            return false;
    }
    int get_f(int v){
        if(f[v] == v)
            return f[v];
        f[v] = get_f(f[v]);
        return f[v];
    }

以下为Accepted代码——Kruskal算法-454ms-排序：结构体内重载小于号

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    #include <cmath>
    
    using namespace std;
    
    const double zero = 1e-4;
    
    struct Edge{
        int u;
        int v;
        int w;
        bool operator < (const Edge &b)const{
            return w < b.w;
        }
    }edge[501400];
    
    struct Node{
        int x;
        int y;
    }node[1014];
    
    int tp, f[1014];
    
    void Init(int n);
    int get_f(int v);
    bool Merge(int u, int v);
    double Dis(int i, int j);
    
    int main(){
        int n, m, i, j, t, num, u, v;
        scanf("%d", &n);
            Init(n);
            for(i = 1; i <= n; i++){
                scanf("%d %d", &node[i].x, &node[i].y);
            }
            t = 0;
            for(i = 1; i <= n; i++){
                for(j = i+1; j <= n; j++){
                    edge[t].u = i, edge[t].v = j;
                    edge[t].w = Dis(i, j);
                    t++;
                }
            }
            sort(edge, edge+t);
    
            num = 0;
            scanf("%d", &m);
            while(m--){
                scanf("%d %d", &u, &v);
                if(Merge(u, v))
                    num++;
            }
            for(i = 0; i < t; i++){
                u = edge[i].u, v = edge[i].v;
                if(Merge(u, v)){
                    printf("%d %d\n", u, v);
                    num++;
                }
                if(num == n-1)
                    break;
            }
    
        return 0;
    }
    void Init(int n){
        for(int i = 1; i <= n; i++)
            f[i] = i;
    }
    double Dis(int i, int j){
        int dx = node[i].x - node[j].x;
        int dy = node[i].y - node[j].y;
        int xy = dx*dx + dy*dy;
        return xy;
    }
    bool Merge(int u, int v){
        int t1 = get_f(u);
        int t2 = get_f(v);
        if(t1 != t2){
            f[t2] = t1;
            return true;
        }
        else
            return false;
    }
    int get_f(int v){
        if(f[v] == v)
            return f[v];
        f[v] = get_f(f[v]);
        return f[v];
    }

[vjudge]: https://vjudge.net/contest/163010#problem/H