MST (minimum spanning tree)

Kruskal's algorithm

// G: graph
// w: weight
MST-Kruskal(G, w)
  A = empty set
  for each vertex v in V[G]
      do Make-Set(v)
  sort the edges of E into nondecreasing order by weight w
  for each edge (u,v) in E, taken in nondecreasing order by weight w
      do if Find-Set(u) != Find-Set(v)
          then A = A union {(u,v)}
               Union(u,v)
  return A // MST

Animation: Kruskal Algorithm

Problem: topcoder RoadReconstruction

Editorial:  This problem can be solved by modification of standard Kruskal algorithm of finding MST (minimal spanning tree) in undirected graph. Cities will be the vertice of that graph, and roads will be its edges. Each damaged road will provide the corresponding edge the weight that equals the cost of the reconstruction. Other (non-damaged) roads will have weight 0.
Now, let's sort all the edges in ascending order of their weights, and in the case of a tie - in the lexicographical order of their identifiers.
The Kruskal algorithm gives us the minimal spanning tree. Finally, to obtain the answer to the problem let's remove all edges that don't need to be reconstructed from MST. Don't forget to sort the remaining identifiers in the lexicographical order!

下面是Zhomart's solution, 注意他对i/o的处理 (sscanf)，customized sort,

#include<iostream>
#include<cstdio>
#include<map>
#include<cmath>
#include<string>
#include<vector>
using namespace std;

struct ROAD {
   int id1,id2,cost;
   char ID[51];
}tr;
map<string,int> names;
vector<ROAD> ed;

char ID[51],STR1[51],STR2[51];
int N,col[51];

bool compare(const ROAD &r1,const ROAD &r2) {
   if( r1.cost!=r2.cost ) return r1.cost<r2.cost;
   return string(r1.ID)<string(r2.ID);
   return false;
}

class RoadReconstruction {
public:
  string selectReconstruction(vector<string> ss) {
     N = 0;
     for(int i=0; i<ss.size(); ++i) {
        ss[i]+=' ';
        tr.cost=0;
        if( sscanf(ss[i].c_str(),"%s %s %s %d",tr.ID,STR1,STR2,&tr.cost)==3 ) tr.cost=0;
        if( names[STR1]==0 ) names[STR1] = ++N;
        if( names[STR2]==0 ) names[STR2] = ++N;
        tr.id1 = names[STR1];
        tr.id2 = names[STR2];
        ed.push_back(tr);
     }

     for(int i=1; i<=N; ++i)
        col[i] = i;

     int M = N;
     sort(ed.begin(),ed.end(),compare);

     string res="";
     vector<string> rr;
     for(int i=0; i<ed.size(); ++i)
        if( col[ ed[i].id1 ] != col[ ed[i].id2 ] ) {
           int ccol = col[ed[i].id1],new_col = col[ed[i].id2];

           //after union, update union id           
           for(int j=1; j<=N; ++j)
              if( col[j]==ccol ) col[j] = new_col;
           // if it is a damaged road
           if( ed[i].cost>0 )
              rr.push_back(ed[i].ID);
           M--; // total set number --, it is supposed to be 1 set left after MST is done
        }
     sort(rr.begin(),rr.end());
     for(int i=0; i<rr.size(); ++i) {
        if( i>0 ) res+=" ";
        res+=rr[i];
     }
     if( M!=1 ) res = "IMPOSSIBLE";

     return res;
  }
};

Prim's algorithm