Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

裸prim 1A 献上板子

Posted by GoZY at 2016-06-04 10:20:23 on Problem 1789
//
//  main.cpp
//  poj 1789 最小生成树prim
//
//  Created by  on 16/6/4.
//  Copyright © 2016年 . All rights reserved.
//

#include <iostream>
#include <cstdio>
#include <cstring>
const int inf = 0x3f3f3f3f;
using namespace std;
int n,m,g[2010][2010];
char s[2010][10];
int prim()
{
    int ans,zmin,i,j,k,dist[2010];
    ans = 0;
    bool b[2010];
    memset(dist,0x3f,sizeof(dist));
    for (i = 1; i <= n; ++i)
    {
        dist[i] = g[1][i];
    }
    memset(b,true,sizeof(b));
    b[1] = false;
    dist[1] = 0;
    for (i = 1; i < n;++i)
    {
        zmin = inf;
        for (j = 1; j <= n; ++j)
        if (b[j] && dist[j] < zmin)
        {
            zmin = dist[j];
            k = j ;
        }
        b[k] = false;
        ans += zmin;
        for (j = 1; j <= n; ++j)
        if (g[k][j] < dist[j])
            dist[j] = g[k][j];
    }
    return ans;
}
int main(int argc, const char * argv[]) {
    int i,j,k;
    while (cin >> n)
    {
        memset(g,0,sizeof(g));
        if (n == 0)
            break;
        for (i = 1; i <= n; ++i)
        {
            scanf("%s",s[i]);
        }
        for (i = 1; i <= n; ++i)
        {
            for (j = 1; j <= n; ++j)
            {
                if (i == j)
                    g[i][j] = 0;
                else
                {
                    int tot = 0;
                    for (k = 0; k < 7; ++k)
                        tot+=(s[i][k]!=s[j][k]);
                    g[i][j] = tot;
                }
            }
        }
        printf("The highest possible quality is 1/%d.\n",prim());
    }
    return 0;
}

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator