Cod sursa(job #1791001)

Utilizator AlexandruRudiAlexandru Rudi AlexandruRudi Data 28 octombrie 2016 23:01:32
Problema Arbore partial de cost minim Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.91 kb
#include <bits/stdc++.h>

using namespace std;

bool comp(pair<int,pair<int,int>> a, pair<int,pair<int,int>> b){
    if(a.first<b.first) return false;
    return true;
}

int n,m,x,y,z,cost,neg;
bool v[200005];
vector <pair<int,int>> g[200005],f;
pair<int,pair<int,int>> mn;
priority_queue <pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,function<bool(pair<int,pair<int,int>>,pair<int,pair<int,int>>)>> q(comp);

int main()
{
    ifstream in("apm.in");
    ofstream out("apm.out");
    in >> n >> m;
    mn={10000,{0,0}};
    for(int i=1;i<=m;i++){
        in >> x >> y >> z;
        g[x].push_back(make_pair(y,z));
        g[y].push_back(make_pair(x,z));
        if(z<mn.first) mn={z,{x,y}};
    }
    q.push(mn); v[mn.second.first]=1; v[mn.second.second]=1;
    while(q.size()){
        mn=q.top();
        q.pop();
        f.push_back({mn.second.first,mn.second.second});
        cost+=mn.first;
        if(!v[mn.second.first]){
            for(int i=0;i<g[mn.second.first].size();i++){
                if(!v[g[mn.second.first][i].first]) q.push({g[mn.second.first][i].second,{mn.second.first,g[mn.second.first][i].first}}),v[g[mn.second.first][i].first]=1;
            }
        }
        if(!v[mn.second.second]){
            v[mn.second.second]=1;
            for(int i=0;i<g[mn.second.second].size();i++){
                if(!v[g[mn.second.second][i].first]) q.push({g[mn.second.second][i].second,{mn.second.second,g[mn.second.second][i].first}}),v[g[mn.second.second][i].first]=1;
            }
        }
        if(f.size()==n-1){
            out << cost << '\n' << f.size() << '\n';
            for(int i=0;i<f.size();i++){
                out << f[i].first << ' ' << f[i].second << '\n';
            }
            return 0;
        }
    }
    out << cost << '\n' << f.size() << '\n';
    for(int i=0;i<f.size();i++){
        out << f[i].first << ' ' << f[i].second << '\n';
    }
}