题目描述
样例输入
5 2
1 2 1
3 4 1
样例输出
2
思路:
CPU在1s之内可以同时执行多条指令.如下图中执行在第1个s中,执行指令0,1,3,在第二个指令中,执行指令2和4.所以结果为2. 我们可以边进行拓扑排序边进行求解最长路径.(因为前驱点完成了自己才能执行)
参考代码
#include<iostream>
#include<stack>
#include<string.h>
using namespace std;
const int maxn = 1000+10;
int map[maxn][maxn],topo[maxn],in[maxn],label[maxn],n,m;//label:标记执行的时间.
stack<int> s;
void TopoSort(){
//int cnt = 0;
for(int i = 0; i < n; i++){
if(!in[i]){//入度为0的进栈
s.push(i);
label[i] = 1;//标记执行时间为1
}
}
while(!s.empty()) {
int x = s.top();
s.pop();
//topo[++cnt] = x;
for(int i = 0;i < n; i++){
if(map[x][i]){
if(label[i] < label[x]+map[x][i]){//最常路径松弛操作.
label[i] = label[x]+map[x][i];
}
in[i]--;
if(!in[i]){
s.push(i);
}
}
}
}
}
int main()
{
int u,v,w, maxt;
while(cin>>n>>m){
//初始化
memset(map,0,sizeof(map));
memset(topo,0,sizeof(topo));
memset(in,0,sizeof(in));
memset(label,0,sizeof(label));
maxt = 0;
for(int i = 1;i <= m; i++){
cin>>u>>v>>w;
map[u][v] = w;
in[v]++;
}
TopoSort();
for(int i = 0; i < n; i++){
if(label[i] > maxt){
maxt = label[i];
}
}
cout<<maxt<<endl;
}
return 0;
}