用到了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;
}