fork download 
  1. #include <stdio.h>
  2. #define oo 1000005
  3. #define MAX_N 100
  4. #define NO_EDGE 0
  5. typedef struct{
  6. 	int n;
  7. 	int A[MAX_N][MAX_N];
  8. }Graph;
  9. void init_graph(Graph *G, int n){
  10. 	G->n = n;
  11. 	int u,v;
  12. 	for(u=1;u<=n;u++){
  13. 		for(v=1;v<=n;v++){
  14. 			G->A[u][v] = 0;
  15. 		}
  16. 	}
  17. }
  18. void add_edge(Graph *G, int u, int v){
  19. 	G->A[u][v]++;
  20. }
  21.  
  22. #define MAX_ELEMENTS 100
  23. typedef int ElementType;
  24. typedef int ElementType;
  25. typedef struct{
  26. 	ElementType data[MAX_ELEMENTS];
  27. 	int size;
  28. }List;
  29.  
  30. void make_null(List *L){
  31. 	L->size = 0;
  32. }
  33. void push_back(List *L, ElementType x){
  34. 	L->data[L->size] = x;
  35. 	L->size++;
  36. }
  37. ElementType element_at(List *L, int i){
  38. 	return L->data[i-1];
  39. }
  40. int count_list(List *L){
  41. 	return L->size;
  42. }
  43. void copy_list(List *L1,List *L2){
  44. 	L2->size = L1->size;
  45. 	int i;
  46. 	for(i=0;i< L1->size;i++){
  47. 		L2->data[i] = L1->data[i];
  48. 	}
  49. }
  50. #define MAX_SIZE 100
  51. typedef int ElementType;
  52. typedef struct{
  53. 	ElementType data[MAX_SIZE];
  54. 	int front, rear;
  55. }Queue;
  56. void make_null_queue(Queue *Q){
  57. 	Q->front = -1;
  58. 	Q->rear = -1;
  59. }
  60. void enqueue(Queue *Q, ElementType u){
  61. 	Q->rear++;
  62. 	Q->data[Q->rear]=u;
  63. }
  64. ElementType front(Queue *Q){
  65. 	return Q->data[Q->front];
  66. }
  67. void dequeue(Queue *Q){
  68. 	Q->front++;
  69. }
  70. int empty(Queue *Q){
  71. 	return Q->front > Q->rear;
  72. }
  73.  
  74. int max(int a, int b){
  75. 	return (a>b)?a:b;
  76. }
  77. int min(int a, int b){
  78. 	return (a<b)?a:b;
  79. }
  80. void topo_sort(Graph *G, List *L){
  81. 	int deg[MAX_N];
  82. 	int u,x,v;
  83. 	//Tinh bac vao cua u
  84. 	for(u=1; u<=G->n;u++){
  85. 		deg[u] = 0;
  86. 		for(x=1;x<=G->n;x++){
  87. 			if(G->A[x][u] != 0)
  88. 				deg[u]++;
  89. 		}
  90. 	}
  91. 	Queue Q;
  92. 	make_null_queue(&Q);
  93. 	for(u=1;u<=G->n;u++){
  94. 		if(deg[u]==0)
  95. 		enqueue(&Q,u);
  96. 	}
  97. 	make_null(L);
  98. 	while(!empty(&Q)){
  99. 		int u = front(&Q);
  100. 		dequeue(&Q);
  101. 		push_back(L,u);
  102. 		for(v=1;v<=G->n;v++){
  103. 			if(G->A[u][v] != 0){
  104. 				deg[v]--;
  105. 				if(deg[v]==0)
  106. 					enqueue(&Q,v);
  107. 			}
  108. 		}
  109. 	}
  110. }
  111.  
  112. int d[MAX_N];
  113. int r[MAX_N];
  114.  
  115. int main(){
  116. 	Graph G;
  117. 	int n,u,x,v,j;
  118. 	int job, time;
  119.  
  120. // 	freopen("dt.txt", "r", stdin);
  121. 	scanf("%d", &n);
  122. 	init_graph(&G, n+2);
  123. 	int alpha = n+1, beta = n+2;
  124. 	d[alpha] = 0;
  125. 	for(u=1;u<=n;u++){
  126. 		scanf("%d", &d[u]);
  127. 		do{
  128. 			scanf("%d", &x);
  129. 			if(x>0) add_edge(&G, x, u);
  130. 		}while(x>0);
  131. 	}
  132. 	scanf("%d %d", &job, &time);
  133.  
  134. 	for(u=1;u<=n;u++){
  135. 		int deg_neg = 0;
  136. 		for(x=1;x<=n;x++){
  137. 			if(G.A[x][u] > 0) deg_neg++;
  138. 		}
  139. 		if(deg_neg == 0) add_edge(&G, alpha, u);
  140. 	}
  141.  
  142. 	for(u=1;u<=n;u++){
  143. 		int deg_pos = 0;
  144. 		for(v=1;v<=n;v++){
  145. 			if(G.A[u][v] > 0) deg_pos++;
  146. 		}
  147. 		if(deg_pos==0) add_edge(&G, u, beta);
  148. 	}
  149. 	List L;
  150. 	topo_sort(&G, &L);
  151.  
  152. 	int t[MAX_N];
  153. 	t[alpha] = 0;
  154. 	for(j=2;j<=L.size;j++){
  155. 		int u = element_at(&L, j);
  156. 		t[u] = 0;
  157. 		for(x=1;x<=G.n;x++){
  158. 			if(G.A[x][u] > 0)
  159. 				t[u] = max(t[u], t[x] + d[x]);
  160. 		}
  161. 	}
  162.  
  163. 	int T[MAX_N];
  164. 	T[beta] = t[beta];
  165.  
  166. 	for(j=L.size-1;j>=1;j--){
  167. 		int u = element_at(&L, j);
  168. 		T[u] = +oo;
  169. 		for(v=1;v<=G.n;v++){
  170. 			if(G.A[u][v] > 0)
  171. 			T[u] = min(T[u], T[v] - d[u]);
  172. 		}
  173. 	}
  174. 	printf("%d\n", T[beta]);
  175. 	for(u=1;u<=G.n;u++){
  176. 		printf("%d-%d\n", t[u], T[u]);
  177. 	}
  178. 	return 0;
  179. }
Success #stdin #stdout 0s 5296KB
comments ()
stdin 
10
7 0
3 1 0
1 2 0
8 1 0
2 3 4 0
1 3 4 0
1 3 4 0
2 6 0
2 8 0
1 5 7 9 0
stdout 
21
0-0
7-11
10-14
7-7
15-18
15-15
15-19
16-16
18-18
20-20
0-0
21-21
https://ideone.com/aFEG8G
language:
C (gcc 8.3)
created:
14 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!