当前位置 博文首页 > 文章内容

    【最小生成树】Arctic Network POJ - 2349

    作者: 栏目:未分类 时间:2020-08-14 18:00:25

    本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
    说我们IIS7站长博客,有一篇博文用了他们的图片。
    要求我们给他们一张图片6000元。要不然法院告我们

    为避免不必要的麻烦,IIS7站长博客,全站内容图片下架、并积极应诉
    博文内容全部不再显示,请需要相关资讯的站长朋友到必应搜索。谢谢!

    另祝:版权碰瓷诈骗团伙,早日弃暗投明。

    相关新闻:借版权之名、行诈骗之实,周某因犯诈骗罪被判处有期徒刑十一年六个月

    叹!百花齐放的时代,渐行渐远!



    Arctic Network POJ - 2349

    题意:

    给定\(n\)个互不相同的长度为\(7\)的字符串,将两个字符串之间的距离定义为两串中字符不同的位置个数,问\(1/Q\)的最大值,其中\(Q=\sum^{t_d}_{t_0}{d({t_0},{t_d})}\)

    思路:

    求的就是最小生成树的总边权……除了距离需要另外算一下以外就是套模板。

    const int maxn = 2000 + 100;
    const int maxm = 4000000 + 100;
    
    int fa[maxn], tmp[maxm];
    int u[maxm], v[maxm];
    int w[maxm];
    int n, m;
    string s[maxn];
    
    int find(int x) { 
        return fa[x] == x ? x : fa[x] = find(fa[x]); 
    }
    bool cmp(int i, int j) {
        return w[i] < w[j];
    }
    
    int count(string s1, string s2) {
        int a = 0;
        for (int i = 0; i < 7; i++) {
            if (s1[i] != s2[i]) a++;
        }
        return a;
    }
    
    double solve() {
        int ans = 0;
        for (int i = 0; i < maxn; i++) fa[i] = i;
        for (int i = 0; i < m; i++) tmp[i] = i;
        sort(tmp, tmp + m, cmp);
        for (int i = 0; i < m; i++) {
            int e = tmp[i];
            int from = find(u[e]);
            int to = find(v[e]);
            if (from != to) {
                ans += w[e];
                fa[from] = to;
            }
        }
        return ans;
    }
    
    int main()
    {
        //ios::sync_with_stdio(false);
        while (cin >> n && n) {
            m = 0;
            for (int i = 1; i <= n; i++) {
                cin >> s[i];
                for (int j = i - 1; j >= 1; j--) {
                    int k = count(s[i], s[j]);
                    u[m] = i; v[m] = j; w[m] = k; m++;
                    u[m] = j; v[m] = i; w[m] = k; m++;
                }
            }
            cout << "The highest possible quality is 1/" << solve() << "." << endl;
        }
        return 0;
    }