1

Тема: Помогите с Крускалом

#include <iostream>
using namespace std;
int p[500000] , r[500000] , n,m,sum;
pair<int , pair<int,int> > a[400000];


int FindSet(int x)
{
    if (p[x]!=x) p[x]= FindSet(p[x]);
    return p[x];
}

void Union(int a,int b)
{
    a=FindSet(a);
    b=FindSet(b);

    if (r[a] > r[b]) p[b] = a; else
    {
        p[a]=b;
        if (r[a] == r[b]) r[b]++;
    }
}

int main()
{
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    cin>>n>>m;

    for (int i=1;i<=n;i++) p[i]=i;
    
    for (int i=0;i<m;i++) {
        int l,r,w;
        cin>>l>>r>>w;
        a[i] = make_pair( w, make_pair(l,r) );
    }

    sort(a,a+m);

    for (int i=m-1;i>=0;i--)
    if (FindSet(a[i].second.second)!=FindSet(a[i].second.first)) {
        Union(a[i].second.second , a[i].second.first);
        sum+=a[i].first;
    } 

    cout<<sum;
}

Пожалуйста помогите с pair! Не могу понять

2

Re: Помогите с Крускалом

Не знаю, какая проблема с пейр, но перебирать ребра нужно по возрастанию веса, а не по убыванию.

3

Re: Помогите с Крускалом

Просто объясните как работает пейр. Я перехожу с паскаля на си++.

4 Отредактировано brainail (2010-01-21 12:59:16)

Re: Помогите с Крускалом

http://msdn.microsoft.com/ru-ru/magazine/cc163451.aspx
http://www.cyberguru.ru/programming/cpp … age18.html

Почитай вот это думаю ты поймёшь,а так pair связывает каких-то две структуры,или сами же pair.
В твоём случае он связывает ценность ребра и направление ребра,поэтому
pair< int, pair< int, int > > - первый int - цена,второй int - откуда,третий int - куда.
Таким же образом pair может связать и большее кол-во структур разного предназначения.. smile
ИМХО! Сам я в си++ не шарю big_smile

5

Re: Помогите с Крускалом

Pair очень просто работает, если есть переменная var типа pair<T1,T2> где T1 и T2 любые типы, то можно обращаться к var.first - типа T1 или к var.second - типа T2. Ну и еще pair'ы сравниваются только по первым элементам из пары(т. е. var.first).

6

Re: Помогите с Крускалом

2 2rf, pair'ы сравниваются не только по первым элементам, а сначала по первым, а в случае равенства их - по вторым. make_pair(1, 2) < make_pair(1, 3)

7

Re: Помогите с Крускалом

Большое всем спасибо! Кто может дать книгу где можно научиться пользоваться СТЛом?

8

Re: Помогите с Крускалом

http://www.softtime.ru/cpp_info/stl.php
Вот.

9

Re: Помогите с Крускалом

Когда мне нужно посмотреть что-нибудь по STL обычно хожу на cplusplus.com .

10

Re: Помогите с Крускалом

Эккель. Философия C++. Введение в стандартный C++ (2-е изд.) (DJVU, 6.4 МБ)
wink