Эта программа дает мне вес минимального остовного дерева и самое длинное расстояние от начального узла. Но после ввода количества тестовых случаев, номера вершины и номера ребра, требуется два ребра и их веса, и это дает некоторое нежелательное значение. ?
#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;
}
программа компилируется отлично. она дает проблемы для более чем двух краев. Я просто не знаю почему. Спасибо
Задача ещё не решена.
Других решений пока нет …