fork download
copy 
  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 d[MAX_N];
  82. 	int u,x,v;
  83. 	//Tinh bac vao cua u
  84. 	for(u=1; u<=G->n;u++){
  85. 		d[u] = 0;
  86. 		for(x=1;x<=G->n;x++){
  87. 			if(G->A[x][u] != 0)
  88. 				d[u]++;
  89. 		}
  90. 	}
  91. 	Queue Q;
  92. 	make_null_queue(&Q);
  93. 	for(u=1;u<=G->n;u++){
  94. 		if(d[u]==0)
  95. 		enqueue(&Q,u);
  96. 	}printf("done u\n");
  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. 				d[v]--;
  105. 				if(d[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,i;
  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. 	for(u=1;u<=n;u++){
  134. 		int deg_neg = 0;
  135. 		for(x=1;x<=n;x++){
  136. 			if(G.A[x][u] > 0) deg_neg++;
  137. 		}
  138. 		if(deg_neg == 0) add_edge(&G, alpha, u);
  139. 	}
  140.  
  141. 	for(u=1;u<=n;u++){
  142. 		int deg_pos = 0;
  143. 		for(v=1;v<=n;v++){
  144. 			if(G.A[u][v] > 0) deg_pos++;
  145. 		}
  146. 		if(deg_pos==0) add_edge(&G, u, beta);
  147. 	}
  148. 	List L;
  149. 	topo_sort(&G, &L);
  150.  
  151. 	int t[MAX_N];
  152. 	t[alpha] = 0;
  153.  
  154. 	for(j=2;j<=L.size;j++){
  155. 		int u = element_at(&L, j);
  156. 		t[u] = -oo;
  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. 	int T[MAX_N];
  163. 	T[beta] = t[beta];
  164. 	for(j=L.size-1;j>=1;j--){
  165. 		int u = element_at(&L, j);
  166. 		T[u] = +oo;
  167. 		for(v=1;v<=G.n;v++){
  168. 			if(G.A[u][v] > 0)
  169. 			T[u] = min(T[u], T[v] - d[u]);
  170. 		}
  171. 	}
  172. 	for(i=0;i<n;i++)
  173. 	printf("%d %d\n", t[i], T[i]);
  174. 	return 0;
  175. }
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
12
14 0
12 1 0
30 2 0
9 2 0
14 3 0
18 3 0
15 3 0
19 3 0
10 6 7 8 0
15 5 9 0
12 4 10 0
4 11 0
4 60
stdout
copy 
done u
https://ideone.com/aAZ9hQ
language:
C (gcc 8.3)
created:
4 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!