lab4

//
//  main.cpp
//  comb_algs3
//
//  Created by Максим Бачурин on 27.03.2018.
//  Copyright © 2018 Максим Бачурин. All rights reserved.
//

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
#include <numeric>

using namespace std;

const int inf = 1e9;

void kruskal() { //O(m log n + n^2)
    int n, m;
    cout << "Введите граф: " << endl;
    cin >> n >> m;
    vector<pair<int, pair<int, int>>> g(m); // вес, первая вершина, вторая
    for(int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        g[i] = {c,{a,b}};
    }
    sort(g.begin(), g.end());
    int cost = 0;
    vector<pair<int, int>> result;
    vector<int> tree_id(n);
    for(int i = 0; i < n; i++) {
        tree_id[i] = i;
    }
    for(int i = 0; i < m; i++) {
        int a = g[i].second.first,
        b = g[i].second.second,
        l = g[i].first;
        if(tree_id[a] != tree_id[b]) {
            cost += l;
            result.push_back({a, b});
            int old_id = tree_id[b], new_id = tree_id[a];
            for(int j = 0; j < n; j++) {
                if(tree_id[j] == old_id) {
                    tree_id[j] = new_id;
                }
            }
        }
    }
    cout << "Минимальный остов: вес: " << cost << endl;
    for(auto x : result) {
        cout << x.first + 1 << " " << x.second + 1 << endl;
    }
}

pair<vector<int>,vector<pair<int, int>>> prim() { // O(n^2)
    vector<pair<int, int>> ans;
    int n, m;
    cout << "Введите граф: " << endl;
    cin >> n >> m;
    vector<vector<int>> g(n);
    for(int i = 0; i < n; i++) {
        g[i].resize(n);
        fill(g[i].begin(), g[i].end(), inf);
    }
    for(int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        a--; b--;
        g[a][b] = c;
        g[b][a] = c;
    }
    vector<bool> used(n);
    vector<int> min_e(n, inf), sel_e(n, -1), cost;
    min_e[0] = 0;
    for(int i = 0; i < n; i++) {
        int v = -1;
        for(int j = 0; j < n; j++) {
            if(!used[j] && (v == -1 || min_e[j] < min_e[v]))
                v = j;
        }
        if (min_e[v] == inf) {
            //cout << "Нет Остова";
            return {{},{}};
        }
        used[v] = true;

        if (sel_e[v] != -1) {
            //cout << v + 1 << " " << sel_e[v] + 1 << endl;
            ans.push_back({v + 1, sel_e[v] + 1});
            cost.push_back(min_e[v]);
        }
        for(int to = 0; to < n; to++) {
            if(g[v][to] < min_e[to]) {
                min_e[to] = g[v][to];
                sel_e[to] = v;
            }
        }
    }
    //cout << "Вес: " << cost << endl;
    return {cost, ans};
}

void solve() {
    auto ans = prim();
    double p = 1;
    for(auto x : ans.first) {
        p *= (1 - (double)x/100);
    }
    p = 1 - p;
    cout << "Лучшая вероятность: " << p << endl;
    for(auto x : ans.second) {
        cout << x.first << " " << x.second << endl;
    }
}

int main() {
    //kruskal();

//    auto ans = prim();
//    cout << "Вес: " << accumulate(ans.first.begin(), ans.first.end(), 0)
//    << endl;
//    for(auto x : ans.second) {
//        cout << x.first << " " << x.second << endl;
//    }
//
    solve();
    return 0;
}

/*
 4 4
 1 2 10
 2 3 10
 3 4 10
 4 1 11

 6 9
 1 2 10
 2 3 2
 1 5 9
 1 6 8
 4 6 3
 5 6 1
 4 5 4
 3 4 5
 2 5 6

 12 24
 1 2 6
 2 3 15
 3 9 6
 1 5 5
 2 5 8
 2 4 18
 1 4 11
 7 8 9
 8 9 14
 7 9 4
 9 10 19
 7 10 13
 8 12 5
 11 12 7
 6 11 3
 5 6 15
 4 6 10
 2 7 11
 3 8 18
 4 11 17
 4 7 7
 5 7 9
 7 11 12
 10 12 2

 4 6
 1 2 10
 2 3 10
 3 4 10
 4 1 10
 1 3 5
 2 4 4
 */