Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2011-03-13

[][]プリム法を有向グラフに使用して失敗した例 04:58 はてなブックマーク - プリム法を有向グラフに使用して失敗した例 - 練習帳

Codeforces Beta Round #17 B. Hierarchy

問題文

 http://www.codeforces.com/problemset/problem/17/B

要約

 n 人の会社で,上司ー部下の関係を n-1 組作る。この関係の候補が m 個与えられていて,社員 a[i] が社員 b[i] を部下にするにはコスト c[i] がかかる(1 <= i <= m)。さらに,各社員には能力値が定められていて,社員 a[i] の能力値は社員 b[i] の能力値より高い事が保証されている。

 合計でかかるコストの最小値を求めよ。

 社員の数 n は 1 以上 1000 以下,候補の数 m は 0 以上 10000 以下,コスト c[i] は 0 以上 10^6 以下,能力値 q[j] は 0 以上 10^6 以下


分析

 最小全域木を求める問題だと思う。能力値 q[i] 達から木構造の根を求め,そこから最小全域木をプリム法で求めるコードが次のもの

コード(c++)
#include <iostream>
#include <vector>
#include <utility>
#include <climits>

using namespace std;

int main(){
  int n;cin >> n;
  int q;
  int mx = 0;int head = 0;
  // 根を求める
  for(int i = 0;i<n;i++){
    cin >> q;
    if(mx < q ) {
      mx = q;
      head = i;
    }
  }

  int m;cin >> m;
  vector<vector<pair<int ,int > > > table(n); // 隣接リスト
  for(int i = 0;i<m;i++){
    int a,b,c;cin >> a >> b >> c;
    a--;b--;
    table[a].push_back(make_pair(b,c));
  }

  int ans = 0;
  vector<int > used(n);
  vector<int > r;      // used[i] = 1 <=> i は r に含まれる 
  r.push_back(head);
  for(int i = 0;i < n-1;i++){
    int fst = -1;
    int next = -1;
    int cost = INT_MAX;
    for(size_t j = 0;j<r.size();j++){
      for(size_t k = 0;k<table[r[j]].size();k++){
	if(used[table[r[j]][k].first] != 0 ) continue;
	if(table[r[j]][k].second < cost){
	  fst =  r[j];
	  cost = table[r[j]][k].second;
	  next = table[r[j]][k].first;
	}	  
      }
    }
    if(next != -1){
      used[next]= 1;
      ans+=cost;
      r.push_back(next);
    }else{
      cout << -1 <<  endl;
      return 0;
    }
  }
  cout << ans <<endl;
  return 0;
}

 すると,次のテストケース (test case 12) で WA

5
3 9 2 1 8
9
2 5 10
1 3 8
3 4 9
5 4 2
2 1 4
5 1 4
2 4 2
1 4 7
5 1 2

 このケースの場合,2→5 (コスト10) と 2→1(コスト4)を比較して 2→1 を選んでしまいますが,1 へ至る道は 2→5 を選んでから 5→1(コスト2)を選ぶのが正しいです。Wikipediaにもこんな記述がありました

In computer science, Prim's algorithm is a greedy algorithm that finds a minimum spanning tree for a connected weighted undirected graph.(Prim’s algorithm - Wikipedia)

 ただ,プリム法を有向グラフに適用する方法もある事はあるみたいです。それを使えば能力値を使わなくてもこの問題を解けるのでしょうか。