不眠熊猫
2019-09-27 16:06
采纳率: 14.3%
浏览 201

关于2014.12 ccf的第四题的一点疑问

用到了krusal,写的感觉逻辑蛮简单,但是跑的结果出现错误,最后就是10分,希望大佬帮忙看看哪里出了问题

图片说明

#include<iostream>

using namespace std;

//将路径从大到小排列 
void sort(int **road,int road_num)
{
    int *temp;
    for(int n=0;n<road_num;n++)
    for(int m=n+1;m<road_num;m++)
    {
        if(road[n][2]>road[m][2])
        {
            temp=road[n];
            road[n]=road[m];
            road[m]=temp;
        }
    }
}

int main() 
{
    int field_num=0,road_num=0;
    cin>>field_num>>road_num;


    int *reach_f=new int [field_num+1];//已经可以灌溉的田地 

    int **road=new int*[road_num];//记录下面输入的内容 

    for(int n=0;n<road_num;n++)
    {
        road[n]=new int[3];
        cin>>road[n][0]>>road[n][1]>>road[n][2];
    }


    int sum=0;//需要的灌溉总路程 

    sort(road,road_num);

    for(int open=0,n=0;open<field_num;n++)//从小到大添加灌溉做需要的路程 (kruskal) 
    {
        if(reach_f[road[n][0]]!=1&&reach_f[road[n][1]]!=1)
        {
            open+=2;reach_f[road[n][0]]=1;reach_f[road[n][1]]=1;sum+=road[n][2];

        }
        else if(reach_f[road[n][0]]!=1&&reach_f[road[n][1]]==1)
        {
            open++;reach_f[road[n][0]]=1;sum+=road[n][2];

        }
        else if(reach_f[road[n][0]]==1&&reach_f[road[n][1]]!=1)
        {
            open++;reach_f[road[n][1]]=1;sum+=road[n][2];

        }
        else
        continue;

    }

    cout<<sum;

    return 0;
} 
  • 写回答
  • 好问题 提建议
  • 追加酬金
  • 关注问题
  • 邀请回答

1条回答 默认 最新

  • JonathanYan 2019-09-27 17:09
    最佳回答

    reach_f没有初始化的原因吧。

    试试这组测试数据
    4 4
    1 2 1
    3 4 1
    1 3 2
    2 4 4

    评论
    解决 无用
    打赏 举报

相关推荐 更多相似问题