SRM313 D1E-D2H ParallelProgramming

TopCoder Statistics - Problem Statement

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.

$i$番目のプロセスは$time[i]$かかって，プロセスの優先順位が与えられる．全てのプロセスが終わる時間を求める．

閉路がある場合，そこでぐるぐるしてしまうのでDAGであるのが全てのプロセスが終わる条件となる．DAGかどうかはトポロジカルソートが完了しているかで見た．もしDAGの場合トポロジカル順序が求まっているので，その順番で$dp[i] := i$番目のプロセスが終わる時間として更新していった．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89

#include <iostream>
#include <sstream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <map>
#include <set>
#include <queue>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int, int> P;

int n;
vector<int> G[55], out;

bool isDAG() {
  int indeg[55];
  memset(indeg, 0, sizeof(indeg));

  rep(i, n) {
      rep(j, G[i].size()) indeg[ G[i][j] ]++;
  }

  queue<int> que;
  rep(i, n) {
      if(indeg[i] == 0) que.push(i);
  }

  while(que.size()) {
      int u = que.front(); que.pop();
      out.push_back(u);

      rep(i, G[u].size()) {
          int v = G[u][i];
          indeg[v]--;

          if(indeg[v] == 0) que.push(v);
      }
  }

  return (out.size() == n);
}

class ParallelProgramming {
  public:
  int minTime(vector <int> time, vector <string> prec) {
      n = time.size();

      out.clear();
      rep(i, 55) G[i].clear();

      rep(i, n) {
          rep(j, n) {
              if(prec[i][j] == 'Y') {
                  G[i].push_back(j);
              }
          }
      }

      if(isDAG()) {
          int dp[55];
          memset(dp, 0, sizeof(dp));

          rep(i, out.size()) {
              int v = out[i];
              dp[v] = max(dp[v], time[v]);

              rep(j, G[v].size()) {
                  int to = G[v][j];
                  dp[to] = max(dp[to], dp[v] + time[to]);
              }
          }

          int ans = 0;
          rep(i, n) ans = max(ans, dp[i]);

          return ans;

      } else return -1;
  }
};
Oct 3rd, 2016
dag, srm, topcoder, グラフ, トポロジカルソート