1 条题解
-
0
参考答案:
#include<iostream> #include<cstring> using namespace std; const int N = 25000; int e[N], ne[N], h[N], idx; int b[N], dis[N]; int q[N]; int n, m; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } bool top_sort() { int hh = 0, tt = -1; for (int i = 1; i <= n; ++i) if (!b[i]) q[++tt] = i; while (hh <= tt) { int t = q[hh++]; for (int i = h[t]; ~i; i = ne[i]) { int j = e[i]; if (--b[j] == 0) { q[++tt] = j; } } } return tt == n - 1; } int main() { memset(h, -1, sizeof(h)); cin >> n >> m; for (int i = 1; i <= m; ++i) { int a, c; cin >> a >> c; add(c, a); b[a]++; } if (!top_sort()) cout << "No answer" << endl; else { for (int i = 1; i <= n; ++i) dis[i] = 100; for (int i = 0; i < n; ++i) { int j = q[i]; for (int k = h[j]; ~k; k = ne[k]) { dis[e[k]] = max(dis[e[k]], dis[j] + 1); } } int res = 0; for (int i = 1; i <= n; ++i) res += dis[i]; cout << res << endl; } return 0; }
- 1
信息
- ID
- 5363
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 10
- 标签
- 递交数
- 8
- 已通过
- 1
- 上传者