Алгоритм Boost C++ prim неправильный ответ

Эта программа дает мне вес минимального остовного дерева и самое длинное расстояние от начального узла. Но после ввода количества тестовых наборов, номера вершины и номера ребра она берет два ребра и их веса и дает какое-то ненужное значение. почему ?

#include<iostream>
#include<boost/config.hpp>
#include<boost/graph/adjacency_list.hpp>
#include<utility>
#include<boost/graph/prim_minimum_spanning_tree.hpp>
#include<vector>


using namespace std;
using namespace boost;

int main()
{
  typedef adjacency_list < vecS, vecS, undirectedS,property < vertex_distance_t, int>, property < edge_weight_t, int > > Graph;
  int no_test=0,v,e,m,a,b,c,w,d;
  cin>>no_test;
  int array_weights[100],array_distances[100],i,j;
  m=0;
  while(m!=no_test)
  {
    w=0;
    d=0;
    cin>>v>>e;//take input

    Graph g(v);//create graph g

    property_map < Graph,edge_weight_t > ::type weightMap;
    bool b;
    typedef graph_traits < Graph> ::edge_descriptor edge11;

    for(i=0;i<e;i++)  //add edges into g from i/p
    {
      edge11 ed;
      cin>>a>>b>>c;
      tie(ed, b)=add_edge(a, b, g);
      weightMap[ed]=c;
    }
    typedef graph_traits < Graph> ::vertex_descriptor vertex11;
    property_map<Graph,vertex_distance_t>::type distanceMap=get(vertex_distance,g);
    property_map<Graph,vertex_index_t>::type indexMap=get(vertex_index,g);
    vector < vertex11 > pred(v);
    prim_minimum_spanning_tree(g,*vertices(g).first,&pred[0],distanceMap,weightMap,indexMap,default_dijkstra_visitor());
    typedef graph_traits<Graph>::edge_iterator edge1;
    typedef graph_traits<Graph>::vertex_iterator vertex1;
    pair <edge1, edge1> edg;

    for(edg=edges(g);edg.first!=edg.second;++edg.first)
    {
      w=w+weightMap[*edg.first];
    }


    pair<vertex1,vertex1> vtx;
    for(vtx=vertices(g);vtx.first!=vtx.second;++vtx.first)
    {
      if(distanceMap[*vtx.first]>d)
      d=distanceMap[*vtx.first];
    }

    array_weights[m]=w;
    array_distances[m]=d;

    m++;
   }

  for(j=0;j<no_test;j++)
  {
    cout<<array_weights[j]<<" "<<array_distances[j]<<endl;
  }
return 0;
}

программа отлично компилируется.выдает проблемы более чем на два ребра.я просто не знаю почему.спасибо


person rama    schedule 19.10.2013    source источник


Ответы (1)


Проблема с вашей программой в том, что она объявляет две переменные с именем b. В начале программа объявляет переменную с именем b типа int. Позже он объявляет переменную с именем b типа bool. Второе объявление закрывает первое объявление.

Когда программа выполняет cin>>a>>b>>c;, она будет использовать b типа bool. Когда вы вводите значение, отличное от 0 или 1 для b, это установит бит ошибки для cin, поскольку значение не может быть проанализировано как bool (ссылка). После этого cin не будет принимать ввод до тех пор, пока не будет вызвано cin.clear(), что сбрасывает бит ошибки. Поскольку ваша программа не вызывает cin.clear(), она больше не будет принимать ввод и выполнять все операции чтения.

Чтобы исправить это, измените объявление bool b; на bool inserted; и измените назначение tie(ed, b) = add_edge(a, b, g); на tie(ed, inserted) = add_edge(a, b, g);.

Кроме того, вы можете добавить дополнительную проверку ошибок каждый раз, когда программа запрашивает ввод. Это можно сделать, проверив результат cin.fail() после каждого ввода. Без таких проверок ваша проблема также возникнет, если пользователь введет недопустимое значение, которое не может быть проанализировано как целое число (например, какая-то строка, такая как abc).

В качестве примечания я бы рекомендовал компилировать с повышенным количеством предупреждений компилятора. Это может помочь вам обнаружить проблемы, такие как выше. Например, компиляция вашей программы с g++ или clang++ с использованием флага -Wall для включения предупреждений приведет к предупреждению о том, что первый b не используется.

person f9c69e9781fa194211448473495534    schedule 10.12.2020