poj 1789 Truck History(kruskyアルゴリズム)

3900 ワード

テーマリンク:http://poj.org/problem?id=1789
思考:1つの点で、2つの行の間に文字の個数が分からないということは、権力と見なされます.そしてkruskyalアルゴリズムで最小生成ツリーを計算します.
二つのコードを書きました.一つは優先列で書きました.しかし、時間が過ぎました.なぜか分かりません.誰かに答えて欲しい.後は配列sortで並べ替えてからACになります.
コード:
配列sort並べ替えACコード:
#include<cstdio>
#include<queue>
#include<algorithm>
#include<iostream>

using namespace std;

struct edge
{
    int from;
    int to;
    int cost;
};


bool cmp(edge e1,edge e2)
{
    return e1.cost<e2.cost;
}

edge node[2001*2001];

int father[2005];
int nn,n;

int find(int x)             //      
{
    if(x!=father[x])
    {
        father[x]=find(father[x]);
    }
    return father[x];
}

void kruskal()
{
    int MST=0;
    for(int i=0;i<2005;i++)
    {
        father[i]=i;
    }
    for(int i=0;i<nn;i++)
    {
        int fx=find(node[i].from);
        int fy=find(node[i].to);
        if(fx!=fy)
        {
            father[fx]=fy;
            MST+=node[i].cost;
        }
    }
    printf("The highest possible quality is 1/%d.
",MST); } int main() { char str[2005][10]; int i,j; while(scanf("%d",&n)==1&&n) { nn=0; for(i=0;i<n;i++) { scanf("%s",str[i]); } for(i=0;i<n;i++) { for(j=0;j<i;j++) { int sum=0; for(int kk=0;kk<7;kk++) { if(str[i][kk]!=str[j][kk]) { sum++; } } node[nn].from=i; node[nn].to=j; node[nn].cost=sum; nn++; } } sort(node,node+nn,cmp); kruskal(); } return 0; }
優先キュータイムアウトコード
#include<cstdio>
#include<queue>
#include<algorithm>
#include<iostream>

using namespace std;

struct edge
{
    friend bool operator<(edge e1,edge e2)
    {
        return e1.cost>e2.cost;
    }
    int from;
    int to;
    int cost;
};

edge e;
priority_queue<edge> Q;
int father[2005];
int nn,n;
int find(int x)
{
    if(x!=father[x])
    {
        father[x]=find(father[x]);
    }
    return father[x];
}

void kruskal()
{
    int MST=0;
    for(int i=0;i<2005;i++)
    {
        father[i]=i;
    }
    int num=0;
    while(!Q.empty()&&num!=nn)
    {
        edge e=Q.top();
        //printf("BBB%d %d %d
",e.from,e.to,e.cost); Q.pop(); int fx=find(e.from); int fy=find(e.to); if(fx!=fy) { father[fx]=fy; MST+=e.cost; num++; } } printf("The highest possible quality is 1/%d.
",MST); } int main() { char str[2005][10]; int i,j; while(scanf("%d",&n)==1&&n) { nn=0; while(!Q.empty()) Q.pop(); for(i=0;i<n;i++) { scanf("%s",str[i]); } for(i=0;i<n;i++) { for(j=0;j<i;j++) { int sum=0; for(int kk=0;kk<7;kk++) { if(str[i][kk]!=str[j][kk]) { sum++; } } nn++; e.from=i; e.to=j; e.cost=sum; Q.push(e); //printf("edge:%d %d %d %d
",e.from,e.to,e.cost,nn); } } kruskal(); } return 0; }
著作権声明:このブログのオリジナル文章、ブログは、同意なしに、転載してはいけません.