2 barcelonaxavi BarcelonaXavi 于 2016.01.23 16:30 提问

poj1251求助,测试数据通过但wrong answer 5C

用的Kruskal算法,没用并查集而是在结构体里多了一个变量判断是否是一个连通量。
结果wrong answer。

#include
#include
using namespace std;

struct in{
int f,n,price;

};

int main()
{
int m=1,are[10000],root=1,i;

while(m!=0)
{
    int total=0,head=1,tail=1,q[1000]={0},mark=1;
    in r[2000];
    int j,k,z,h,g,x,flag=1,s;
    char c,d;


    total=0;
    scanf("%d",&m);
    if(m==0) break;
    for(i=1;i<=m-1;i++)
  {
    scanf("\n%c",&c);
    z=c-'A'+1;
    scanf("%d",&g);
   for(j=1;j<=g;j++)
    {

        scanf("\n%c%d",&d,&k);

        h=d-'A'+1;
        r[flag].price=k;
        r[flag].f=z;
        r[flag].n=h;
        flag++;
    }



  }
   flag--;
  for(i=1;i<=flag;i++)                                   //排序;
  for(j=1;j<=flag-i;j++)
  {
    if(r[j].price>r[j+1].price)
    {
        r[j].price=r[j].price+r[j+1].price;
        r[j+1].price=r[j].price-r[j+1].price;
        r[j].price=r[j].price-r[j+1].price;

        r[j].f=r[j].f+r[j+1].f;
        r[j+1].f=r[j].f-r[j+1].f;
        r[j].f=r[j].f-r[j+1].f;

        r[j].n=r[j].n+r[j+1].n;
        r[j+1].n=r[j].n-r[j+1].n;
        r[j].n=r[j].n-r[j+1].n;
    }
  }


  for(i=1;i<=flag;i++)
 {                                            //判断是否是一个连通分量


    if(q[r[i].n]==0&&q[r[i].f]==0)
    {
        total=total+r[i].price;
        q[r[i].n]=mark;
        q[r[i].f]=mark;
        mark++;
        continue;


    }

    if(q[r[i].n]!=q[r[i].f])
    {
        total=total+r[i].price;
        if(q[r[i].n]==0)
        {
            q[r[i].n]=q[r[i].f];

        }
        else if(q[r[i].f]==0)
        {
            q[r[i].f]=q[r[i].n];

        }
        else if(q[r[i].n]!=0&&q[r[i].f]!=0)
        {
            for(j=1;j<=26;j++)
          {
            if(q[j]==q[r[i].f])
            q[j]=q[r[i].n];

          } 
        }


    }


 }
 are[root]=total;
 root++;
}
root--;
for(i=1;i<=root;i++)
{
    printf("%d",are[i]);
    if(i<root) printf("\n");
}

}

2个回答

caozhy
caozhy   Ds   Rxr 2016.01.24 01:30
BarcelonaXavi
BarcelonaXavi   2016.01.24 17:00

我是想知道我的哪错了 谢谢

Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!