题目分析

本题的核心是找到一种卡车类型的派生方案，使得派生计划的质量最高。根据题目定义，质量是所有派生步骤距离之和的倒数，因此需要最小化总距离之和。这可以转化为图论中的**最小生成树（MST）**问题。

关键思路

1. 问题转化：将每个卡车类型视为图中的一个节点，任意两个节点之间的边权为它们代码的汉明距离（不同字符位置的数量）。题目要求的最优派生计划对应这个图的最小生成树。

2. 算法选择：使用Kruskal算法求解最小生成树。该算法按边权从小到大选择边，确保不形成环，直到所有节点连通。

3. 优化策略：

   • 使用并查集（Union-Find）高效检测环。
   • 预处理所有边的权值，避免重复计算。

代码解析

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=2005;
char str[maxn][7];
int pre[maxn];
struct truck
{
    int to;
    int from;
    int weight;
} pp[maxn*(maxn>>1)];
int n,qq,ans;
void init()
{
    ans=0;
    qq=0;
    for(int i=0; i<=n; i++)
        pre[i]=i;
}
bool cmp(truck a,truck b)
{
    return a.weight<b.weight;
}
int finds(int x)
{
    if(x==pre[x])
        return pre[x];
    pre[x]=finds(pre[x]);
    return pre[x];
}
void make_tree()
{
    for(int i=0; i<n; i++)
        for(int j=n-1; j>=i; j--)
        {
            int sum=0;
            for(int x=0; x<7; x++)
                if(str[i][x]!=str[j][x])
                    sum++;
            pp[qq].from=i;
            pp[qq].to=j;
            pp[qq].weight=sum;
            ++qq;
        }
}
void kruskal()
{
    sort(pp,pp+qq,cmp);
    int to,from;
    for(int i=0; i<qq; i++)
    {
        to=finds(pp[i].to);
        from=finds(pp[i].from);
        if(to==from);
        else if(to!=from)
        {
            pre[to]=from;
            ans+=pp[i].weight;
        }
    }
}
int main()
{
    while(~scanf("%d",&n)&&n)
    {
        for(int i=0; i<n; i++)
            scanf("%s",str[i]);
        init();
        make_tree();
        kruskal();
        printf("The highest possible quality is 1/%d.\n",ans);
    }
    return 0;
}

算法步骤详解

1. 输入处理：读取每个测试用例的卡车类型数量和代码。

2. 边生成：make_tree()函数计算任意两个卡车代码之间的汉明距离，并存储所有边的信息。

3. 边排序：使用sort()函数按边权从小到大排序。

4. Kruskal算法：

   • 初始化并查集，每个节点的父节点为自身。
   • 按边权从小到大遍历边，若边的两个端点不在同一集合中，则合并这两个集合，并累加边权。

5. 输出结果：最小生成树的总边权即为Q，输出格式化结果。

复杂度分析

• 时间复杂度：

  • 生成边：O(N²×7)
  • 排序边：O(N² log N)
  • Kruskal算法：O(N² α(N))，α为阿克曼函数的反函数，近似常数
  • 总体复杂度：O(N² log N)

• 空间复杂度：O(N²)，存储所有边。