题目描述
某市为了提高市民文化素质，决定实行普及高中教育，为此要建一所超级大规模的高中以供该市初中毕业的学生就读。我们将完成这所学校的建设看成一个大的工程，事实上建一所学校有许多的子工程，我们把这些子工程编号为1、2、……、N，子工程之间就会有一些依赖关系，即一些子工程必须在某些子工程完成之后才能施工。由于子工程之间有相互依赖关系，因此，有两个任务需要我们去完成：首先，我们需要计算完成这所学校的建设整个工程最少的完成时间；同时，由于一些不可预测的客观因素会使某些子工程延期，因此我们必须知道哪些子工程的延期会影响整个工程的延期，我们集中精力管理好这些子工程，尽量避免这些子工程延期，达到用最快的速度完成整个工程。为了使于编程，现在我们假设：
（1）根据预算，每一个子工程都有一个完成时间；
（2）子工程之间的依赖关系是：部分子工程必须在一些子工程完成之后才开工。
（3）只要满足子工程之间的依赖关系，在任何时刻可以有任何多个子工程同时在施工，也即同时施工的子工程个数不受限制。
（4）整个工程的完成是指：所有子工程的完成。
思路
我们先设一个工程的子工程有一条连向它的边
一开始想的是用一个优先队列来维护入度为0中的最小时间的点
想了想可能会T
然后就改用两个队列弹弹弹的做法，具体见代码
然后就按照拓扑一样跑就可以了
对于第二问，看了看数据范围只有200，想着跑n边上面说的算法应该也不会超时
对于每一个点，如果我们加一，然后时最后的答案变化的话，这个点就是要求的点之一
真是太暴力了
#include#include using namespace std; #define N 100000 #define min(x, y) ((x) < (y) ? (x) : (y)) int l = 0; struct edge { int to, next; }e[N]; int ls[N], a[500], in[500], n, b[500], in1[500]; struct cmp { bool operator()(int x, int y) { return a[x] > a[y]; } }; queue t; queue h; void add(int x, int y) { e[++l] = (edge) {y, ls[x]}; ls[x] = l; } int ans = 0; int bfs() { while (!t.empty()) { int now, mi = 0x7f7f7f7f; while (!t.empty()) { int ll = t.front(); if (mi > a[ll]) { mi = a[ll]; now = ll; } h.push(ll); t.pop(); } ans += a[now]; n--; while (!h.empty()) { int ll = h.front(); if (ll != now) a[ll] -= a[now]; h.pop(); if (ll != now) t.push(ll); } for (int i = ls[now]; i; i = e[i].next) { in[e[i].to]--; if (in[e[i].to] == 0) t.push(e[i].to); } a[now] = 0; } } int main() { int m; scanf("%d", &n); m = n; for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); b[i] = a[i]; } for (int i = 1; i <= n; i++) for (int j = 1; j < n; j++) { int x; scanf("%d", &x); if (x == 1) { if (j >= i) add(j + 1, i); else add(j, i); in[i]++; } } for (int i = 1; i <= n; i++) { if (in[i] == 0) t.push(i); in1[i] = in[i]; } bfs(); if (n != 0) ans = -1; printf("%d\n", ans); int ll = ans; if (n == 0) { n = m; for (int i = 1; i <= n; i++) { while (!t.empty()) t.pop(); while (!h.empty()) h.pop(); n = m; for (int j = 1; j <= n; j++) { if (i == j) a[j] = b[j] + 1; else a[j] = b[j]; in[j] = in1[j]; } for (int j = 1; j <= n; j++) if (in[j] == 0) t.push(j); ans = 0; bfs(); if (ans > ll) printf("%d ", i); n = m; } } }
]]>
Comments NOTHING