Search on the blog

2010年11月16日火曜日

トポロジカルソート

今日は、SRMの過去問をトポロジカルソートで解いてみた。
有向グラフのトポロジーに注目したソートですが、トポロジーって一体・・・、
なんか他にも似たような言葉がたくさんあるような・・・。

ちょっとまとめてみます。
  • トポロジー   幾何学的な相対位置、ネットワークの接続状況など
  • エントロピー 物事の煩雑さ
  • オントロジー 物事の概念を意味・関係などで定義したもの
で、今回はトポロジカルソートです。
簡単に言うと、どの接点も自分の子孫より先に来るようにソートすることです。
Makeでコンパイルする順序を決めたり、PERTのスケジュール管理で使われるみたいです。

ではさっそく解いてみます。
問題は、こちら。

ソースは、これ。
定型的なアルゴリズムがあるようですが、とりあえず、自己流で出力辺の無い接点を取り出して、その接点はグラフ集合からのぞいて・・・を繰り返しています。



bool dn[64];
class CorporationSalary {
public:
long long totalSalary(vector<string> relations) {
memset(dn, 0, sizeof(dn));

VI idx;
int sz = relations.size();
while (accumulate(dn, dn+sz, 0) < sz) {
REP(i, relations.size()) {
if (dn[i]) continue;
bool lst = true;
REP(j, relations[i].size()) {
if (dn[j]) continue;
if (relations[i][j] == 'Y') {
lst = false;
break;
}
}
if (lst) {
idx.PB(i);
dn[i] = 1;
}
}
}

long long ret = 0LL;
long long sl[sz];
fill(sl, sl+sz, 0LL);

REP(i, sz) {
long long m = 0LL;
REP(j, sz) {
if (relations[idx[i]][j] == 'Y')
m += sl[j];
}
sl[idx[i]] = m ? m : 1;
ret += sl[idx[i]];
}
return ret;
}
};

0 件のコメント:

コメントを投稿