Página Principal

MC521-1s2014

MC621-2s2014

MC521-1s2015

MC621-2s2015

MC521-1s2016

Conteúdo

Área Reservada

edit sidebar

SPOJBRREDOTICA

Autor: Guilherme Andrade

#include <iostream>
#include <vector>
#include <string>
#include <queue>
using namespace std;

class Edge{
public:
        int i, j, w;
        Edge(int i, int j, int w):i(i), j(j), w(w) {}
};

class EdgeComp{
public:
        bool operator()(const Edge& a, const Edge& b){
                return a.w > b.w;
        }
};

class Graph{
        vector< vector<Edge> > adj;
        const int n;
        vector<Edge> MSTEdges;
        void MST();
public:
        Graph(int n):n(n) { adj.resize(n); MSTEdges.reserve(2*n);}
        void printEdges(){
                MST();
                for(int i=0; i < MSTEdges.size(); ++i){
                        if ( MSTEdges[i].i < MSTEdges[i].j )
                                cout << MSTEdges[i].i + 1<< " " << MSTEdges[i].j + 1<< endl;
                        else
                                cout << MSTEdges[i].j + 1<< " " << MSTEdges[i].i + 1<< endl;
                }
        }
        void addEdge(int i, int j, int w){
                adj[i].push_back( Edge(i,j,w) );
                adj[j].push_back( Edge(j,i,w) );
        }

};

void Graph::MST(){

        priority_queue<Edge, vector<Edge>, EdgeComp> q;
        vector<bool> visited(n);
        int auxNode = 0;
        visited[auxNode] = true;
        int countedEdges = 0;

        while ( countedEdges < n-1 ){

                for(int i=0; i < adj[auxNode].size(); ++i){
                        if ( !visited[ adj[auxNode][i].j ] ){
                                q.push( adj[auxNode][i] );
                        }
                }

                while(true){
                        Edge e = q.top();
                        q.pop();

                        if  ( !visited[ e.j ] ){
                                auxNode = e.j;
                                visited[e.j] = true;
                                ++countedEdges;
                                MSTEdges.push_back( e );
                                break;
                        }

                }
        }
}

int main(){
        int testCase = 0;
        while (true) {
                int n,m;
                cin >> n >> m;
                if (n == 0)
                        break;
                Graph g(n);
                for(int i=0; i < m; ++i){
                        int x,y,w;
                        cin >> x >> y >> w;
                        g.addEdge(x-1, y-1, w);
                }

                if (testCase == 0){
                        cout << "Teste " << ++testCase << endl;
                        g.printEdges();
                }
                else{
                        cout << "\nTeste " << ++testCase << endl;
                        g.printEdges();
                }
        }
        return 0;
}