読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

aoj 0072

灯篭 | Aizu Online Judge
最小全域木のコストを求めさせる問題.
プリムのアルゴリズムを用いる.
Spaghetti Source - 最小全域木 (Prim)

typedef int Weight;
struct Edge
{
  int src, dst;
  Weight weight;
  Edge(int src, int dst, Weight weight) :
    src(src), dst(dst), weight(weight) { }
};
typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;
typedef vector<Array> Matrix;
bool operator < (const Edge &e, const Edge &f)
{
  return e.weight != f.weight ? e.weight > f.weight :
    e.src != f.src ? e.src < f.src : e.dst < f.dst;
}
/*
最小全域木 (Prim)
const Graph &g
  グラフ.隣接リスト.
  vector<vector<Edge>>
int r
  Prim 法の始点.この点を根とする全域木を求める.
  全域木に入る辺集合.
戻り値
  最小全域木の重みと最小全域木の辺集合のペア.
*/
pair<Weight, Edges> minimumSpanningTree(const Graph &g, int r = 0)
{
  int n = g.size();
  Edges T;
  Weight total = 0;
  vector<bool> visited(n); // 訪れたか? default false
  priority_queue<Edge> Q;
  Q.push( Edge(-1,r,0) ); // 始点
  while (!Q.empty())
  {
    Edge e = Q.top(); Q.pop();
    if (visited[e.dst]) continue;
    T.push_back(e);
    total += e.weight;
    visited[e.dst] = true;
    for(auto f : g[e.dst]) if (!visited[f->dst]) Q.push(f);
  }
  return pair<Weight, Edges>(total, T);
}

それで本体はこれだけ.

int main()
{
  int n;
  while(cin >> n,n)
  {
    Graph g(n);
    int m; cin >> m;
    REP(i,m)
    {
      int s,d,w;scanf("%d,%d,%d\n",&s,&d,&w);
      g[s].push_back(Edge(s,d,w/100-1));
      g[d].push_back(Edge(d,s,w/100-1));
    }
    cout << minimumSpanningTree(g).first << endl;
  }
  return 0;
}