題意：給定一系列任務(wù)的依賴關(guān)系以及完成每個(gè)任務(wù)需要花費(fèi)的時(shí)間，問(wèn)一些任務(wù)的最晚完成時(shí)間和最早完成時(shí)間差值。
解法：根據(jù)依賴關(guān)系建立正反兩個(gè)圖，分別表示該任務(wù)動(dòng)工之前需要完成哪些任務(wù)和哪些任務(wù)需要在該任務(wù)完成之后開始動(dòng)工，然后兩次dfs，分別標(biāo)記任務(wù)，
然后剩下的沒(méi)有標(biāo)記的任務(wù)的就是完成時(shí)間就是所需要求的答案（具體見(jiàn)代碼）。
#include <stdio.h>
#include <string.h>
#define N 505
bool g[N][N], gb[N][N], mk1[N], mk2[N];
int v[N];
void dfs1(int u, int n)
{
mk1[u] = 1;
for(int i = 1; i <= n; i++)
if(!mk1[i] && g[u][i])
dfs1(i, n);
}
void dfs2(int u, int n)
{
mk2[u] = 1;
for(int i = 1; i <= n; i++)
if(!mk2[i] && gb[u][i])
dfs2(i, n);
}
int main()
{
int n, m, a, b, cas = 1;
while(scanf("%d %d", &n, &m), n + m)
{
memset(g, 0, sizeof(g));
memset(gb, 0, sizeof(gb));
for(int i = 1; i <= n; i++)
scanf("%d", &v[i]);
for(int i = 0; i < m; i++)
{
scanf("%d %d", &a, &b);
g[a][b] = 1;
gb[b][a] = 1;
}
scanf("%d", &m);
printf("Case #%d:\n", cas++);
for(int i = 0; i < m; i++)
{
scanf("%d", &a);
memset(mk1, 0, sizeof(mk1));
memset(mk2, 0, sizeof(mk2));
dfs1(a, n);
dfs2(a, n);
int count = 0;
for(int j = 1; j <= n; j++)
{
if(!mk1[j] && !mk2[j])
{
count += v[j];
}
}
printf("%d\n", count);
}
puts("");
}
return 0;
}