トポロジカルソート

今日は、SRMの過去問をトポロジカルソートで解いてみた。

有向グラフのトポロジーに注目したソートですが、トポロジーって一体・・・、

なんか他にも似たような言葉がたくさんあるような・・・。

ちょっとまとめてみます。

• トポロジー　　 幾何学的な相対位置、ネットワークの接続状況など
• エントロピー　物事の煩雑さ
• オントロジー　物事の概念を意味・関係などで定義したもの

で、今回はトポロジカルソートです。

簡単に言うと、どの接点も自分の子孫より先に来るようにソートすることです。

Makeでコンパイルする順序を決めたり、PERTのスケジュール管理で使われるみたいです。

ではさっそく解いてみます。

問題は、こちら。

http://www.topcoder.com/stat?c=problem_statement&pm=9824&rd=12179

ソースは、これ。

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

view plainprint?

1. bool dn[64];  
2. class CorporationSalary {  
3. public:  
4.  long long totalSalary(vector<string> relations) {  
5.      memset(dn, 0, sizeof(dn));  
6.   
7.      VI idx;  
8.      int sz = relations.size();  
9.      while (accumulate(dn, dn+sz, 0) < sz) {  
10.          REP(i, relations.size()) {  
11.              if (dn[i]) continue;  
12.              bool lst = true;  
13.              REP(j, relations[i].size()) {  
14.                  if (dn[j]) continue;  
15.                  if (relations[i][j] == 'Y') {  
16.                      lst = false;  
17.                      break;  
18.                  }  
19.              }  
20.              if (lst) {  
21.                  idx.PB(i);  
22.                  dn[i] = 1;  
23.              }  
24.          }  
25.      }  
26.   
27.      long long ret = 0LL;  
28.      long long sl[sz];  
29.      fill(sl, sl+sz, 0LL);  
30.   
31.      REP(i, sz) {  
32.          long long m = 0LL;  
33.          REP(j, sz) {  
34.              if (relations[idx[i]][j] == 'Y')  
35.                  m += sl[j];  
36.          }  
37.          sl[idx[i]] = m ? m : 1;  
38.          ret += sl[idx[i]];  
39.      }  
40.      return ret;  
41.  }  
42. };  

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