2

这个程序给了我最小生成树的权重和到起始节点的最长距离..但是在输入测试用例的数量和顶点数和边数后，它需要两条边和它们的权重，它给出了一些垃圾值。为什么?

#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;
}

该程序编译完美。它给两个以上的边缘带来了问题。我只是不知道为什么。谢谢

4

1 回答 1

1

您的程序的问题在于它声明了两个带有 name 的变量b。程序开始时声明了一个名为btype的变量int。稍后它声明了一个b类型为 name 的变量bool。第二个声明隐藏第一个声明。

当程序执行cin>>a>>b>>c;时，它将使用bof 类型bool。当您输入0或以外的值1时b，这将为 设置故障位cin，因为该值不能被解析为bool（参考）。在此之后，在被调用cin之前不会接受输入cin.clear()，这会重置故障位。由于您的程序不调用cin.clear()，它将不再接受输入并运行所有读取操作。

要解决此问题，请更改bool b;to的声明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未使用的警告。

于 2020-12-10T23:24:17.307 回答