- 软件开发
- 求关键路径*CriticalPath
#include <cstdio>
#include <algorithm>
#include <vector>
#include <stack>
#define INF 0x7FFFFFFF
using namespace std
;
typedef struct Arcnode
{ int w
, adj
, E
, L
; }Arcnode
;
int N
, M
, S
, T
, a
;
vector
<int> vE
, vL
, inDegree
, tOrder
, isCritical
;
vector
<vector
<Arcnode
>> G
;
bool TopologicalOrder()
{
stack
<int> s
;
for( int i
= 0; i
< N
; ++i
)
if( !inDegree
[i
] )
s
.push( i
);
while( !s
.empty() )
{
int v
= s
.top();
tOrder
.push_back( v
);
s
.pop();
for( auto iarc
= G
[v
].begin(); iarc
!= G
[v
].end(); ++iarc
)
if( !(--inDegree
[iarc
->adj
]) )
s
.push( iarc
->adj
);
}
if( tOrder
.size() == N
)
return true;
return false;
}
void GetCriticalPath()
{
isCritical
[0] = 1;
for( int i
= 0; i
< N
; ++i
)
for( auto iarc
= G
[ tOrder
[i
] ].begin(); iarc
!= G
[ tOrder
[i
] ].end(); ++iarc
)
if( vE
[ iarc
->adj
] < vE
[ tOrder
[i
] ] + iarc
->w
)
vE
[ iarc
->adj
] = vE
[ tOrder
[i
] ] + iarc
->w
;
vL
[ tOrder
[ N
- 1 ] ] = vE
[ tOrder
[ N
- 1 ] ];
for( int i
= N
- 1; i
>= 0; --i
)
for( auto iarc
= G
[ tOrder
[i
] ].begin(); iarc
!= G
[ tOrder
[i
] ].end(); ++iarc
)
if( vL
[ tOrder
[i
] ] > vL
[ iarc
->adj
] - iarc
->w
)
vL
[ tOrder
[i
] ] = vL
[ iarc
->adj
] - iarc
->w
;
for( int i
= 0; i
< N
; ++i
)
for( auto iarc
= G
[i
].begin(); iarc
!= G
[i
].end(); ++iarc
)
{
iarc
->E
= vE
[i
];
iarc
->L
= vL
[ iarc
->adj
] - iarc
->w
;
if( iarc
->E
== iarc
->L
)
isCritical
[ iarc
->adj
] = 1;
}
}
int main()
{
Arcnode temp
;
scanf("%d %d", &N
, &M
);
G
.resize(N
);
vE
.resize(N
);
vL
.resize(N
);
isCritical
.resize(N
);
inDegree
.resize(N
);
fill( vL
.begin(), vL
.end(), INF
);
for( int i
= 0; i
< M
; ++i
)
{
scanf("%d %d %d", &a
, &temp
.adj
, &temp
.w
);
G
[a
].push_back(temp
);
++inDegree
[temp
.adj
];
}
if( !TopologicalOrder() )
return -1;
GetCriticalPath();
for( int i
= 0; i
< N
; ++i
)
if( isCritical
[ tOrder
[i
] ] )
printf("%d ", tOrder
[i
]);
}
测试用例：
9 12
0 1 0
0 2 0
1 3 4
2 4 3
3 5 2
3 6 7
4 5 3
4 7 6
5 6 3
5 7 2
6 8 0
7 8 0
