F - Truck History——最小生成树_Prim算法

怼烎@ 2022-06-11 00:15 110阅读 0赞

Think:  
1知识点：最小生成树\_Prim算法  
2思考：字符串组最优生成  
3题意分析：为使得1/Σ(to,td)d(to,td)最大，分子部分为1的状态使得分母最小即可，即生成所有“卡车种类”的最短距离和最小  
4相同类型题目博客分享：[博客： B - 英语考试 FZU - 2254——最小生成树 ][B - _ FZU - 2254_]

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int inf = 0x3f3f3f3f;
    
    int e[2014][2014], vis[2014], dis[2014];
    char st[2014][14];
    
    void Prim(int n);
    
    int main(){
        int n, i, j, k, cnt;
        while(scanf("%d", &n) && n){
            getchar();
            for(i = 1; i <= n; i++)
                scanf("%s", st[i]);
            for(i = 1; i <= n; i++){
                e[i][i] = 0;
                for(j = i+1; j <= n; j++){
                    cnt = 0;
                    for(k = 0; k < 7; k++){
                        if(st[i][k] != st[j][k])
                            cnt++;
                    }
                    e[i][j] = e[j][i] = cnt;
                }
            }
            Prim(n);
        }
        return 0;
    }
    void Prim(int n){
        int i, miv, v, num, sum;
        memset(vis, 0, sizeof(vis));
        for(i = 1; i <= n; i++)
            dis[i] = e[1][i];
        vis[1] = 1, dis[1] = 0, num = 1, sum = 0;
        while(num < n){
            miv = inf;
            for(i =1; i <= n; i++){
                if(!vis[i] && dis[i] < miv){
                    miv = dis[i], v = i;
                }
            }
            vis[v] = 1, num++, sum += dis[v];
            for(i = 1; i <= n; i++){
                if(!vis[i] && e[v][i] < dis[i])
                    dis[i] = e[v][i];
            }
        }
        printf("The highest possible quality is 1/%d.\n", sum);
    }

[B - _ FZU - 2254_]: http://blog.csdn.net/blessingxry/article/details/76038488
[vjudge]: https://vjudge.net/contest/163010#problem/F