关键路径入门题目
举个例子:
约束条件: 我约了两个朋友A,G去网吧打游戏,要三个人一起到了才开始打,我们约好三个人12点同时到达,我和友人A约好一起去网吧,G单独去网吧(G12点准时抵达)
友人A是六点钟起床,那么我(我这个事件)最早开始去网吧(这个活动)的时间就是六点, 因为A六点钟起床,我最早是在6点和A同时去网吧.
A起床后,那么6,7,8...点我们都可以去网吧,但是我们去了网吧朋友G还不在(G12点到达),就不能打游戏会很无聊,所以我们何必那么早去呢? 我们会尽可能晚去,在12点出发刚刚好和G同时抵达网吧.
要是13点去,那么我们本来是打算12点开始打游戏的, 打游戏这个活动就变成了13点开始,向后推迟了.
综上,我和A同时去网吧这个活动,最早开始时间是6点, 最迟开始时间是12点
做法:
拓扑排序 每次选入度为0的点
顶点表示事件，弧表示活动
只有当一个事件(也就是点)的入度为0 才能开始这个事件
假设一个点A 入度为1 被另一个点x用一条权值为w的边指着
那么事件点A要先等x做完 再等w的时间才能开始执行 这个过程所需时间 是 x+w
以此类推 一个点被n个点分别用n条弧指着 他的最早开始执行时间是 X[i] + W[i] 里边的最大值 即把全部指向他的事件和活动(点和弧) 做完了才能开始
实现 在拓扑的排序的时候 取出节点now 每次边指向的节点都判断 他的开始时间finish最迟是什么时候
最后finish中最大的就是完成所有活动所需的时间
http://acm.hdu.edu.cn/showproblem.php?pid=4109
#include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<vector> #include<algorithm> using namespace std; struct node { int to,value; }; vector<node> nxt[1005]; //向量+结构体 邻接表 int in_degree[1005]; //节点的入度 int finish[1005]; //节点的开始时间 int m, n; void topo() { queue <int> q; for (int i = 0; i < n; i++) if (in_degree[i] == 0) { finish[i] = 1; q.push(i); } while (!q.empty()) { int now = q.front(); q.pop(); for (int i = 0; i < nxt[now].size(); i++) { int to = nxt[now][i].to; int v = nxt[now][i].value; in_degree[to]--; finish[to] = max(finish[to], finish[now] + v); if (in_degree[to] == 0) q.push(to); } } int tp = 1; for (int i = 0; i < n; i++) { tp = max(tp, finish[i]); } printf("%d ", tp); } int main() { while (cin >> n >> m) { fill(finish, finish + 1005, 0); fill(in_degree, in_degree + 1005, 0); for(int i = 0; i < n; i++) nxt[i].clear(); for (int i = 0; i < m; i++) { int a, b, c; scanf("%d %d %d", &a, &b, &c); in_degree[b]++; node no; no.to = b; no.value = c; nxt[a].push_back(no); } topo(); } return 0; }