P1113 杂务

考点

• 拓扑排序

题解

#include <bits/stdc++.h>
using namespace std;
const int LEN = 1e4 + 50;
//每个任务的前置任务中的最大时间开销，每个任务的时间开销，每个任务的入度
int n, mx[LEN], val[LEN], ind[LEN];
vector<int> e[LEN];
queue<int> q;

void toposort() {
  int rt;
  for (int i = 1; i <= n; ++i) {
    if (ind[i] == 0) {
      rt = i;
      break;
    }
  }
  q.emplace(rt);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0, sz = e[u].size(); i < sz; ++i) {
      int v = e[u][i];
      //取前置任务开销里最大的
      mx[v] = max(mx[v], val[u]);
      if (--ind[v] == 0) {
        val[v] += mx[v];
        q.emplace(v);
      }
    }
  }
}

int main() {
  int a, b, c;
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    cin >> a >> b;
    val[a] = b;
    while (cin >> c && c) {
      e[c].emplace_back(a);
      ++ind[a];
    }
  }
  toposort();
  int ans = 0;
  for (int i = 1; i <= n; ++i) ans = max(ans, val[i]);
  cout << ans;
  return 0;
}

思路

拓扑排序的模板题，直接上《深基》的图解便于理解，只不过书上用DFS实现，我用的Kahn