-2

Пытаюсь сдать задачу:

http://informatics.mccme.ru/mod/statements/view3.php?id=261&chapterid=185

Надо вывести длину всех ребер мин. остова. Пишу сразу за m log(n).

Граф связный задан списком смежности. Где же ошибка?

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>

using namespace std;

int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    std::ios::sync_with_stdio(false);
    cin.tie(false);
    int n,m;//кол-во вершин, кол-во ребер
    cin >> n >> m;
    vector< vector< pair<int,int> > >v(n);
    for(int i=0;i<m;++i){//список смежности
        int v1,v2,weight;//вершина1, вершина2, вес ребра между ними(длина)
        cin >> v1 >> v2 >> weight;
        v[v1-1].push_back(make_pair(v2-1,weight));
        v[v2-1].push_back(make_pair(v1-1,weight));
    }
    set< pair<int,int> > u; //обход (длина=dl, вершина)
    vector<int> dl(n,-1); //длина от остова до вершин.
    //стартуем с 0
    dl[0]=0;
    u.insert(make_pair(0,0));
    int result = 0; //длина всех ребер мин остова
    while(!u.empty()){ //обход за n log(m)
        int k = u.begin()->second;
        result += u.begin()->first;//добавляем длину
        u.erase(u.begin());

        for(int j=0;j<v[k].size();++j){
            int i=v[k][j].first, len=v[k][j].second;
            if(dl[i]==-1 || dl[i]>len){
                u.erase(make_pair(dl[i],i));
                dl[i] = len;
                u.insert(make_pair(dl[i],i));
            }
        }
    }
    cout<<result;
    return 0;
}
1
  • Вопросы с просьбами помочь с отладкой («почему этот код не работает?») должны включать желаемое поведение, конкретную проблему или ошибку и минимальный код для её воспроизведения прямо в вопросе. Вопросы без явного описания проблемы бесполезны для остальных посетителей.
    – Kromster
    13 янв 2016 в 13:22

1 ответ 1

1

Вот рабочий Алгоритм Прима за n log(m):

#include <iostream>
#include <cstdio>
#include <vector>
#include <set>

using namespace std;

int main(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    std::ios::sync_with_stdio(false);
    cin.tie(false);
    int n,m;//кол-во вершин, кол-во ребер
    cin >> n >> m;
    vector< vector< pair<int,int> > >v(n);
    for(int i=0;i<m;++i){//список смежности
        int v1,v2,weight;//вершина1, вершина2, вес ребра между ними(длина)
        cin >> v1 >> v2 >> weight;
        v[v1-1].push_back(make_pair(v2-1,weight));
        v[v2-1].push_back(make_pair(v1-1,weight));
    }
    set< pair<int,int> > u; //обход (длина=dl, вершина)
    vector<int> dl(n,-1); //длина от остова до вершин.
    vector<int> used(n);
    //стартуем с 0
    dl[0]=0;
    u.insert(make_pair(0,0));
    int result = 0; //длина всех ребер мин остова
    while(!u.empty()){ //обход за n log(m)
        int k = u.begin()->second;
        result += u.begin()->first;//добавляем длину
        u.erase(u.begin());
        used[k]=1;
        for(int j=0;j<v[k].size();++j){
            int i=v[k][j].first, len=v[k][j].second;
            if(!used[i] && (dl[i]==-1 || dl[i]>len)){
                u.erase(make_pair(dl[i],i));
                dl[i] = len;
                u.insert(make_pair(dl[i],i));
            }
        }
    }
    cout<<result;
    return 0;
}
0

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.