Максимальное значение связующего дерева, неправильное значение с алгоритмом простых чисел - PullRequest
Новая
       18

Максимальное значение связующего дерева, неправильное значение с алгоритмом простых чисел

0 голосов
/ 27 октября 2019 
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

class Record
{
public:
    int des;
    double w;
};

void process();
double Prims(int[1002][1002],int,int,double[1002][1002]);
int arr[1002][1002];
double cost[1002][1002];

bool operator<(const Record &a,const Record &b)
{
    return a.w<=b.w;
}
int main()
{
    freopen("prims.txt","r",stdin);
    process();
    return 0;
}
void process()
{
    int testCase,i,vertexNum,edgeNum,a,b,c,ind,j;
    while(cin>>testCase)
    {
        if(testCase==0)
            break;
        for(i=1;i<=testCase;i++)
        {
            cin>>vertexNum>>edgeNum;
            ind=1;
            for(j=1;j<=edgeNum;j++)
            {
                cin>>a>>b>>c;
                arr[a][b]=1;
                arr[b][a]=1;
                cost[a][b]=c;
                cost[b][a]=c;
            }
            double d=Prims(arr,vertexNum,edgeNum,cost);
            cout<<d<<endl;
        }
    }
}
double Prims(int arr[1002][1002],int vertexNum,int edgeNum,double cost[1002][1002])
{
    double m,t;
    int d[1002],i,j;
    priority_queue<Record,vector<Record>,less<Record> >pq;
    vector<Record>v;
    Record temp;

    for(i=0;i<=vertexNum;i++)
        d[i]=0;
    v.clear();
    i=1;
    for(j=1;j<=vertexNum;j++)
    {
        if(arr[i][j]==1&&d[j]==0){
            temp.des=j;
            temp.w=cost[i][j];
            v.push_back(temp);
            pq.push(v[i-1]);}
    }
    d[i]=1;
    m=0.0;
    while(!pq.empty())
    {
        i=pq.top().des;
        t=pq.top().w;
        pq.pop();
        if(d[i]==0)
        {
            m=m+t;
            cout<<"i: "<<i<<endl;
            cout<<"w: "<<t<<endl;
            for(j=1;j<=vertexNum;j++)
            {
                //cout<<"j: "<<j<<" d[j]: "<<d[j]<<endl;
                if(arr[i][j]==1&&d[j]==0&&i!=j){
                    temp.des=j;
                    cout<<"j: "<<j<<endl;
                    temp.w=cost[i][j];
                    cout<<"cost[i][j]: "<<cost[i][j]<<endl;
                    v.push_back(temp);
                    pq.push(v[(int)v.size()-1]);}
            }
            d[i]=1;
        }
    }
    return m;
}

prims.txt
1
9 14
1 2 4
1 8 8
2 3 8
2 8 11
3 4 7
3 6 4
3 9 2
4 5 9
4 6 14
5 6 10
6 7 2
7 8 1
8 9 7
9 7 6

Максимальное значение связующего дерева должно быть 71. Может кто-нибудь выяснить проблему в коде?

...