Instrction Arrangement(hdu4109)[拓扑排序+dp]
Description
有n个指令m个要求 例如 X,Y,Z 代表 指令Y必须在指令X后Z秒执行 输出cpu运行的最小时间运行最小时间 也就是要满足最大的时间要求
input
输入由多个测试用例组成
第一行有两个整数 N，M （N <= 1000，M <= 10000），表示存在 N 指令和 M 依赖关系。
以下 M 行包含三个整数 X、Y、Z，表示 X 和 Y 之间的安全距离为 Z，Y 应在 X 之后运行。指令编号为 0 到 N - 1。
output
打印一个整数，这是 CPU 需要运行的最短时间。
Sample
5 2
1 2 1
3 4 1
2
分析
限制条件是 y 必须在 x 后多少秒执行,同时一个y可能包含在多组限制条件里,把限制条件当成一条单向边,所有限制条件会构成一张图
因为如果 y 在 x 后,y就不可能有一条边连到x前,整张图就是DAG,可以拓扑排序.
定义dp[i]，表示执行指令i的最早时间，则有：dp[i]=max(dp[i],dp[j]+a[j][i]),a[j][i]表示i必须在j执行后a[j][i]秒执行
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10005;
stack<int> stk;
struct edge{
int to, nx, w;
}e[maxn];
int n, m, len, ans = 1, head[maxn], rd[maxn], dp[maxn];
void insert(int x, int y, int w){//插边
e[++len].to = y;
e[len].nx = head[x];
e[len].w = w;
head[x] = len;
}
void kahn(){//kahn算法
stack<int> stk;
for(int i=1; i<=n; i++)
if(!rd[i]){//入度为零,进栈
stk.push(i);
dp[i] = 1;
}
while(!stk.empty()){
int u = stk.top();//取出栈顶入度为0的点
stk.pop();
for(int i=head[u]; i; i=e[i].nx){
int v = e[i].to, w = e[i].w;
rd[v] --;
dp[v] = max(dp[v], dp[u] + w);//如果有多个限制条件,必须满足最远的那个
ans = max(ans, dp[v]);
if(!rd[v]) stk.push(v);
}
}
}
int main(){
while(scanf("%d%d", &n, &m) != EOF){
memset(head, 0, sizeof(head));
memset(rd, 0, sizeof(rd));
len = 0;
for(int i=1; i<=m; i++){
int x, y, w; scanf("%d%d%d", &x, &y, &w);
insert(x, y, w);
rd[y] ++;
}
kahn();
printf("%d
", ans);
}
return 0;
}