Página Principal

MC521-1s2014

MC621-2s2014

MC521-1s2015

MC621-2s2015

MC521-1s2016

Conteúdo

Área Reservada

edit sidebar

LA 6622

Autor: Guilherme Andrade

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
#include <numeric>
#include <cstdio>
using namespace std;

vector< vector<int> > m;

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> > edges;

        priority_queue<Edge, vector<Edge>, EdgeComp> distsOrdered;


        vector<Edge> solution;
        int n;
        bool isMST;
public:
        Graph(int n, bool isMST=false):n(n),isMST(isMST) {
                edges.resize(n);
        }
        void addEdge(int i, int j, int w){



                if (isMST){
                        solution.push_back( Edge(i,j,w) );
                }

                else
                        distsOrdered.push(Edge(i,j,w));

                edges[i].push_back( Edge(i,j,w) );
                edges[j].push_back( Edge(j,i,w) );
        }
        Graph prim(){
                priority_queue<Edge, vector<Edge>, EdgeComp> q;

                int currentNode = 0;
                vector<bool> visited(n);
                visited[currentNode] = true;
                Graph m(n,true);
                int totalEdgesMST = n-1;
                while(totalEdgesMST--){
                        for(int i=0; i < edges[i].size(); ++i){
                                if ( !visited[ edges[currentNode][i].j ] ){
                                        q.push( edges[currentNode][i] );
                                }
                        }
                        while( visited[ q.top().j ] ){
                                q.pop();
                        }
                        Edge e = q.top();
                        q.pop();
                        visited[e.j] = true;
                        currentNode = e.j;
                        m.addEdge(e.i, e.j, e.w);
                }
                return m;
        };
        int distanceFrom(int x, int y){

                if (x == y)
                        return 0;

                vector<bool> visited(n);
                visited[x] = true;
                vector<int> dists;
                dists.reserve(2*n);
                stack<int> s;
                s.push(x);             
                while(true){
                        bool found=false;
                        int currentNode = s.top();
                        for(int i=0; i < edges[currentNode].size() && !found; ++i){
                                Edge e = edges[currentNode][i];
                                if ( !visited[e.j] ){
                                        visited[e.j] = true;
                                        dists.push_back( e.w );
                                        s.push(e.j);
                                        found = true;
                                }
                        }

                        if (!found){
                                dists.pop_back();
                                s.pop();
                        }
                        else if ( s.top() == y)
                                break;
                }

                return accumulate( dists.begin(), dists.end(), 0 );

        }
        void printSolution(){
                for(int i=0; i < solution.size(); ++i)
                        cout << solution[i].i+1 << " "<< solution[i].j+1 <<" " << solution[i].w << endl;
        }


        void solve(){
                Graph mst = prim();
                int x = 0, y = 1;
                int w = 1000000;
                while(!distsOrdered.empty()){

                        Edge e = distsOrdered.top();
                        distsOrdered.pop();


                                if ( e.w < mst.distanceFrom(e.i,e.j) || mst.distanceFrom(e.i,e.j) > 1000000 ){
                                        w = e.w;
                                        x = e.i;
                                        y = e.j;
                                        break;
                                }
                }

                mst.addEdge(x,y,m[x][y]);

                mst.printSolution();
        }
};



int main(){
        int n;
        bool firstCase = true;
        while ( cin >> n ){
                Graph g(n);
                m.clear();
                m.resize(n);
                for(int i=0; i < n; ++i)
                        m[i].resize(n);
                for(int i=0; i < n; ++i)
                        for(int j=0; j < n; ++j){
                                cin >> m[i][j];
                                if ( j > i)
                                        g.addEdge(i,j,m[i][j]);
                        }


                if (!firstCase){
                        cout <<"\n";
                }
                else{
                        firstCase = false;
                }

                g.solve();
        }
        return 0;
}