B - 英语考试 FZU - 2254——最小生成树

r囧r小猫 2022-06-12 14:21 87阅读 0赞

Think:  
1知识点：并查集  
2题意思考：将每一个单词视为一个结点，两点之间的权值即为联想背这两个单词的精力，这样背过n个单词即可认为将n个结点生成一棵树  
3反思：初始化注意结点范围

[vjudge题目链接][vjudge]

以下为Wrong Answer代码——初始化范围错误

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 1e3 + 2e4;
    const int M = 1040000;
    
    struct Edge{
        int u;
        int v;
        int w;
    }edge[M];
    
    int tp, f[N];
    char st[N][14];
    
    bool cmp(struct Edge a, struct Edge b){
        return a.w < b.w;
    }
    
    void Init(int n);
    int get_f(int v);
    bool Merge(int u, int v);
    
    int main(){
        int n, m, w, i, j, k;
        while(~scanf("%d %d %d", &n, &m, &w)){
            getchar();
            tp = 0;
            for(i = 0; i < n; i++)
                scanf("%s", st[i]);
            for(i = 0; i < n; i++){
                for(j = i+1; j < n; j++){
                    int cnt = 0;
                    for(k = 0; k < m; k++){
                        if(st[i][k] != st[j][k])
                            cnt++;
                    }
                    int t;
                    t = min(m, cnt*w);
                    edge[tp].u = i, edge[tp].v = j, edge[tp].w = t;
                    tp++;
                }
            }
            sort(edge, edge+tp, cmp);
    
            Init(n);
            int ans = 0, sum = 0;
            for(i = 0; i < tp; i++){
                if(Merge(edge[i].u, edge[i].v)){
                    sum += edge[i].w;
                    ans++;
                }
                if(ans == n-1)
                    break;
            }
            sum += m;
            printf("%d\n", sum);
        }
        return 0;
    }
    void Init(int n){
        for(int i = 1; i <= n; i++)
            f[i] = i;
    }
    int get_f(int v){
        if(f[v] == v)
            return f[v];
        f[v] = get_f(f[v]);
        return f[v];
    }
    bool Merge(int u, int v){
        int t1 = get_f(u);
        int t2 = get_f(v);
        if(t1 == t2)
            return false;
        else {
            f[t2] = t1;
            return true;
        }
    }

以下为Accepted代码——Kruskal算法\_156ms

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 1e3 + 2e4;
    const int M = 1040000;
    
    struct Edge{
        int u;
        int v;
        int w;
    }edge[M];
    
    int tp, f[N];
    char st[N][14];
    
    bool cmp(struct Edge a, struct Edge b){
        return a.w < b.w;
    }
    
    void Init(int n);
    int get_f(int v);
    bool Merge(int u, int v);
    
    int main(){
        int n, m, w, i, j, k;
        while(~scanf("%d %d %d", &n, &m, &w)){
            getchar();
            tp = 0;
            for(i = 1; i <= n; i++)
                scanf("%s", st[i]);
            for(i = 1; i <= n; i++){
                for(j = i+1; j <= n; j++){
                    int cnt = 0;
                    for(k = 0; k < m; k++){
                        if(st[i][k] != st[j][k])
                            cnt++;
                    }
                    int t;
                    t = min(m, cnt*w);
                    edge[tp].u = i, edge[tp].v = j, edge[tp].w = t;
                    tp++;
                }
            }
            sort(edge, edge+tp, cmp);
    
            Init(n);
            int ans = 0, sum = 0;
            for(i = 0; i < tp; i++){
                if(Merge(edge[i].u, edge[i].v)){
                    sum += edge[i].w;
                    ans++;
                }
                if(ans == n-1)
                    break;
            }
            sum += m;
            printf("%d\n", sum);
        }
        return 0;
    }
    void Init(int n){
        for(int i = 1; i <= n; i++)
            f[i] = i;
    }
    int get_f(int v){
        if(f[v] == v)
            return f[v];
        f[v] = get_f(f[v]);
        return f[v];
    }
    bool Merge(int u, int v){
        int t1 = get_f(u);
        int t2 = get_f(v);
        if(t1 == t2)
            return false;
        else {
            f[t2] = t1;
            return true;
        }
    }

以下为Accepted代码——Prim算法\_15ms

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    const int N = 1e3 + 4e2;
    
    int vis[N], dis[N], e[N][N];
    char st[N][14];
    
    void Prim(int n, int m);
    
    int main(){
        int n, m, w, i, j, k;
        while(~scanf("%d %d %d", &n, &m, &w)){
            getchar();
            for(i = 1; i <= n; i++)
                scanf("%s", st[i]);
            for(i = 1; i <= n; i++){
                for(j = i; j <= n; j++){
                    if(i == j)
                        e[i][j] = inf;
                    else {
                        int cnt = 0;
                        for(k = 0; k < m; k++){
                            if(st[i][k] != st[j][k])
                                cnt++;
                        }
                        int t = min(m, cnt*w);
                        e[i][j] = e[j][i] = t;
                    }
                }
            }
            Prim(n, m);
        }
        return 0;
    }
    void Prim(int n, int m){
        int i, num, miv, v, sum;
        memset(vis, 0, sizeof(vis));
        for(i = 1; i <= n; i++)
            dis[i] = e[1][i];
        vis[1] = 1, num = 1, sum = 0;
        while(num < n){
            miv = inf;
            for(i = 1; i <= n; i++){
                if(!vis[i] && miv > dis[i]){
                    miv = dis[i];
                    v = i;
                }
            }
            vis[v] = 1, sum += dis[v], num++;
            for(i = 1; i <= n; i++){
                if(!vis[i] && dis[i] > e[v][i])
                    dis[i] = e[v][i];
            }
        }
        printf("%d\n", sum+m);
    }

[vjudge]: https://vjudge.net/contest/173353#problem/B