[관건 적 인 경로] [토폴로지 정렬 + 역 토폴로지 정렬] [회전]

https://blog.csdn.net/haskei/article/details/53749380
구체 적 인 알고리즘 설명 은 다음 과 같다. 1. e 개의 호 를 입력 하여 AOE - 망 의 저장 구 조 를 구축한다.2． 토폴로지 정렬, 그리고 ve [] 를 구 합 니 다.원점 V0 에서 출발 하여 ve [0] = 0 을 토폴로지 에 따라 나머지 각 정점 의 최초 발생 시간 ve [i] 를 질서 있 게 구한다.만약 에 얻 은 토폴로지 질서 서열 에서 정점 개 수 는 네트워크 의 정점 n 보다 작 으 면 네트워크 에 고리 가 존재 하고 관건 적 인 경 로 를 구 할 수 없 으 며 알고리즘 이 종 료 됩 니 다.그렇지 않 으 면 실행 절차 3.3． 토폴로지 역순, vl [] 을 구하 다.외환 점 Vn 에서 출발 하여 vl [n - 1] = ve [n - 1] 를 역 토폴로지 에 따라 나머지 각 정점 의 가장 늦 은 발생 시간 vl [i] 을 질서 있 게 구한다.4． 관건 적 인 경 로 를 구하 다.각 정점 의 ve 와 vl 값 에 따라 각 호 s 의 최초 시작 시간 e (s) 와 늦어도 시작 시간 l (s) 을 구하 십시오.만약 에 특정한 아크 가 조건 e (s) = l (s) 를 만족 시 키 면 관건 적 인 활동 이다.
역순 토폴로지 질서 있 는 서열 의 순서에 따라 각 정점 의 vl 값 을 계산 하기 위해 토폴로지 정렬 과정 에서 구 하 는 토폴로지 질서 있 는 서열 을 기록 해 야 한다. 그러면 토폴로지 정렬 알고리즘 에 스 택 을 추가 하여 토폴로지 질서 있 는 서열 을 기록 하고 각 정점 의 ve 값 을 계산 한 후에 스 택 꼭대기 에서 스 택 밑 까지 역 토폴로지 질서 있 는 서열 이 어야 한다.

  1 #include
  2 #include
  3 #include
  4 #include
  5 #include<string>
  6 #include
  7 #include 
  8 
  9 using namespace std;
 10 
 11 typedef long long ll;
 12 const int maxm = 20;
 13 const int maxn = 100;
 14 const int inf = 0x3f3f3f3f;
 15 struct node {
 16     int x, y, w;
 17     int next;
 18 };
 19 node edge[maxm];
 20 int n, m;
 21 int head[maxn];
 22 //e           , l         , ve[i]         , vl[i]          ,indegree[i]      
 23 //          e，l    ，          ，             ，        ，            
 24 int e, l, ve[maxn], vl[maxn], indegree[maxn];
 25 stack<int> s, t; //s          ，t        ，           
 26 
 27 int TopologicalSort() {
 28     int i, cnt = 0;
 29     for(i=1; i<=n; ++i) //         
 30         if(!indegree[i]) {
 31             t.push(i);
 32             ++cnt;
 33             //printf("%d ", i);
 34         }
 35     while(!t.empty()) {
 36         int a = t.top();
 37         s.push(a);
 38         //printf("%d ", a);
 39         t.pop();
 40         //              ，           
 41         int k = head[a];
 42         while(k != -1) {
 43             if(!--indegree[edge[k].y]) {//       ，     ，   
 44                 t.push(edge[k].y);
 45                 ++cnt;
 46                 //printf("%d ", edge[k].y);
 47             }
 48             if(ve[edge[k].y] < ve[a] + edge[k].w) //               ve[i]， edge[k].y      
 49                 ve[edge[k].y] = ve[a] + edge[k].w;
 50             k = edge[k].next;    
 51         }
 52     }
 53     if(cnt < n) 
 54         return 0;
 55     return 1;
 56 }
 57 
 58 
 59 int main()
 60 {
 61     int i;
 62     memset(head, -1, sizeof(head));
 63     scanf("%d%d", &n, &m);
 64     
 65     //      
 66     for(i=1; i<=m; ++i) {
 67         scanf("%d%d%d", &edge[i].x, &edge[i].y, &edge[i].w);
 68         ++indegree[edge[i].y];  //        
 69         edge[i].next = head[edge[i].x];
 70         head[edge[i].x] = i;
 71     }
 72     
 73     if(TopologicalSort() == 0) { //  TopologicalSort()         ve    
 74         printf("       ,   
");
 75         return 0;
 76     }
 77     
 78     memset(vl, inf, sizeof(vl));
 79     vl[n] = ve[n]; //                      ，        ，           ，          
 80     while(!s.empty()) { //      vl[i] 
 81         int a = s.top();
 82         s.pop();
 83         int k = head[a];
 84         while(k != -1) {
 85             if(vl[a] > vl[edge[k].y] - edge[k].w) {
 86                 vl[a] = vl[edge[k].y] - edge[k].w;
 87             }
 88             k = edge[k].next;
 89         }
 90     }
 91     printf("
    (         ) :
");
 92     for(i=1; i<=n; ++i)  { 
 93         int k = head[i];
 94         while(k != -1) {
 95             e = ve[i]; //          ，                                 
 96             //         
 97             l = vl[edge[k].y] - edge[k].w;
 98             if(l == e)
 99                 printf("%d %d %d
", i, edge[k].y, edge[k].w);
100             k = edge[k].next;
101         }
102     }
103     return 0;
104 }
105 /*
106 9 11
107 1 2 6
108 1 3 4
109 1 4 5
110 2 5 1
111 3 5 1
112 4 6 2
113 5 7 9
114 5 8 7
115 6 8 4
116 7 9 2
117 8 9 4
118 */

 
다음으로 전송:https://www.cnblogs.com/MekakuCityActor/p/9005461.html