08-圖9 關鍵活動 (30 分)

假定一個工程項目由一組子任務構成，子任務之間有的可以并行執行，有的必須在完成了其它一些子任務后才能執行。“任務調度”包括一組子任務、以及每個子任務可以執行所依賴的子任務集。

比如完成一個專業的所有課程學習和畢業設計可以看成一個本科生要完成的一項工程，各門課程可以看成是子任務。有些課程可以同時開設，比如英語和C程序設計，它們沒有必須先修哪門的約束；有些課程則不可以同時開設，因為它們有先后的依賴關系，比如C程序設計和數據結構兩門課，必須先學習前者。

但是需要注意的是，對一組子任務，并不是任意的任務調度都是一個可行的方案。比如方案中存在“子任務A依賴于子任務B，子任務B依賴于子任務C，子任務C又依賴于子任務A”，那么這三個任務哪個都不能先執行，這就是一個不可行的方案。

任務調度問題中，如果還給出了完成每個子任務需要的時間，則我們可以算出完成整個工程需要的最短時間。在這些子任務中，有些任務即使推遲幾天完成，也不會影響全局的工期；但是有些任務必須準時完成，否則整個項目的工期就要因此延誤，這種任務就叫“關鍵活動”。

請編寫程序判定一個給定的工程項目的任務調度是否可行；如果該調度方案可行，則計算完成整個工程項目需要的最短時間，并輸出所有的關鍵活動。

輸入格式:

輸入第1行給出兩個正整數N(≤)和M，其中N是任務交接點（即銜接相互依賴的兩個子任務的節點，例如：若任務2要在任務1完成后才開始，則兩任務之間必有一個交接點）的數量。交接點按1~N編號，M是子任務的數量，依次編號為1~M。隨后M行，每行給出了3個正整數，分別是該任務開始和完成涉及的交接點編號以及該任務所需的時間，整數間用空格分隔。

輸出格式:

如果任務調度不可行，則輸出0；否則第1行輸出完成整個工程項目需要的時間，第2行開始輸出所有關鍵活動，每個關鍵活動占一行，按格式“V->W”輸出，其中V和W為該任務開始和完成涉及的交接點編號。關鍵活動輸出的順序規則是：任務開始的交接點編號小者優先，起點編號相同時，與輸入時任務的順序相反。

輸入樣例:

7 8
1 2 4
1 3 3
2 4 5
3 4 3
4 5 1
4 6 6
5 7 5
6 7 2

輸出樣例:

17
1->2
2->4
4->6
6->7

#include<cstdio>
#include<cstring>
const int maxn = 110;
const int INF = 100000000;int map[maxn][maxn];
int indegree[maxn],outdegree[maxn];
int earliest[maxn],latest[maxn];void init(int n){for(int i = 1; i <= n; i++){for(int j = 1; j <= n; j++){map[i][j] = -1;}indegree[i] = 0;outdegree[i] = 0;earliest[i] = 0;latest[i] = INF;}
}int max(int a,int b){return a > b ? a : b;
}int min(int a,int b){return a < b ? a : b;
}int early_time(int n){int queue[n];int front = -1, rear = -1;for(int i = 1; i <= n; i++){if(indegree[i] == 0){queue[++rear] = i;}}int cnt = 0;while(front < rear){int v = queue[++front];cnt++;for(int i = 1; i <= n; i++){if(map[v][i] >= 0){indegree[i]--;earliest[i] = max(earliest[i],earliest[v]+map[v][i]);if(indegree[i] == 0){queue[++rear] = i;}}}}int ans = 0;if(cnt != n) ans = -1;else{ans = earliest[0];for(int i = 1; i <= n; i++){if(ans < earliest[i]) ans = earliest[i];}}return ans;
}void late_time(int n,int x){int queue[n];int front = -1,rear = -1;for(int i = n; i >= 1; i--){if(outdegree[i] == 0){queue[++rear] = i;latest[i] = x;}}while(front < rear){int v = queue[++front];for(int i = n; i >= 1; i--){if(map[i][v] >= 0){outdegree[i]--;latest[i] = min(latest[i],latest[v]-map[i][v]);if(outdegree[i] == 0){queue[++rear] = i;}}}}
}int main(){int n,m;scanf("%d%d",&n,&m);init(n);int v,u,w;for(int i = 0; i < m; i++){scanf("%d%d%d",&u,&v,&w);map[u][v] = w;indegree[v]++;outdegree[u]++;}int flag = early_time(n);if(flag == -1) printf("0\n");else{printf("%d\n",flag);late_time(n,flag);for(int i = 1; i <= n; i++){if(earliest[i] != latest[i]) continue;for(int j = n; j >= 1; j--){if(map[i][j] >= 0 && earliest[j] == latest[j] && (latest[j] - earliest[i] == map[i][j]))printf("%d->%d\n",i,j); }}}return 0;
}

?