Posted on 2008-08-18 21:45
Hero 閱讀(209)
評論(0) 編輯 收藏 引用 所屬分類:
代碼如詩－－ACM
1 //Accepted 100 From 054100526 － P1105 CPP
2
3 //拓撲排序
4
5 #include <stdio.h>
6 #include <stdlib.h>
7 #include <string.h>
8
9 const int size = 300 ;
10
11 int edge[size][size] ;
12 int indeg[size] ;
13 int cindeg[size] ;
14 int outdeg[size] ;
15
16 int C[size] ;//最初狀態(tài)
17 int U[size] ;//闕值
18 int W[size][size] ;
19 int toporder[size] ;
20 int ct_out ;
21
22 int inn ; int inp ;
23
24 void input()
25 {
26 memset( edge, 0, sizeof(edge) ) ;
27 memset( indeg, 0, sizeof(indeg) ) ;
28 memset( outdeg, 0, sizeof(outdeg) ) ;
29 memset( W, 0, sizeof(W) ) ;
30 int sn, en, w ;
31 for( int i=1; i<=inn; i++ ) {
32 scanf( "%d %d", &C[i], &U[i] ) ;
33 }
34 for( int i=1; i<=inp; i++ ) {
35 scanf( "%d %d %d", &sn, &en, &w ) ;
36 edge[sn][en] = 1 ; W[sn][en] = w ;
37 indeg[en]++ ; cindeg[en]++ ; outdeg[sn]++ ;
38 }
39 }
40
41 void f_indeg()
42 {
43 for( int sn=1; sn<=inn; sn++ ) {
44 for( int en=1; en<=inn; en++ ) {
45 if( edge[en][sn] ) indeg[sn]++ ;
46 }
47 edge[sn][sn] = 0 ;
48 }//構建indeg[]入度
49 }
50
51 int Topsort()
52 {//用棧輸出單一拓撲排序
53 int stack[size] ; int top = -1 ;
54 for( int i=1; i<=inn; i++ ) {
55 if( 0 == indeg[i] ) stack[++top] = i ;
56 }//建立入度為0的棧stack[]
57
58 int cnt_node = 0 ; ct_out = -1 ;
59 while( top >= 0 )
60 {
61 //printf( "%d\n", stack[top] ) ;
62 int curnode = stack[top--] ; //indeg[curnode] = -1 ;//容易忘記
63 toporder[++ct_out] = curnode ; cnt_node++ ;
64
65 for( int j=1; j<=inn; j++ )
66 {
67 if( edge[curnode][j] )
68 {
69 indeg[j]-- ;
70 if( 0 == indeg[j] ) stack[++top] = j ;
71 }//不要忘了加大括號--WA了好多
72 }
73 }
74
75 if( cnt_node < inn ) { printf( "Topsort error--cycle!\n" ) ; return 0 ; }
76
77 return 1 ;
78 }
79
80 void process()
81 {
82 //f_indeg() ;
83
84 Topsort() ;
85
86 for( int sn=0; sn<=ct_out; sn++ ) {
87 if( 0 == cindeg[toporder[sn]] ) continue ;
88 for( int i=0; i<sn; i++ ) {//注意C[i]>0才能傳狀態(tài)
89 if( 1 == edge[toporder[i]][toporder[sn]] && C[toporder[i]]>0 ) {
90 C[toporder[sn]] += W[toporder[i]][toporder[sn]]*C[toporder[i]] ;
91 }
92 }
93 C[toporder[sn]] -= U[toporder[sn]] ;
94 }
95
96 }
97
98 void output()
99 {
100 int cnt = 0 ;
101 for( int i=1; i<=inn; i++ )
102 {
103 if( 0 == outdeg[i] && C[i] > 0 ) {
104 printf( "%d %d\n", i, C[i] ) ; cnt++ ;
105 }
106 }
107 if( 0 == cnt ) printf( "NULL\n" ) ;
108 }
109
110 int main()
111 {
112 while( scanf( "%d %d", &inn, &inp ) != EOF )
113 {
114 input() ;
115
116 process() ;
117
118 output() ;
119 }
120
121 return 0 ;
122 }
123