fork download
copy 
  1. #include <iostream>
  2. #include <cstdio>
  3. #include <algorithm>
  4. #include<sstream>
  5. #include<queue>
  6. #include<vector>
  7. #include<stdio.h>
  8. #include<deque>
  9. #include<string>
  10. #include<cstdio>
  11. #include<memory.h>
  12. using namespace std;
  13. int f,C, P;
  14. vector<vector<int> > AdjList;
  15. int Flow[1500][1500], p[1500];
  16. void updatePath(int t, int minEdge) {
  17. 	if (t == 1)
  18. 	{
  19. 		f = minEdge;
  20. 		return;
  21. 	}
  22. 	else if (p[t] != -1) {
  23. 		updatePath(p[t], min(minEdge, Flow[p[t]][t]));
  24. 		Flow[p[t]][t] -= f;
  25. 		Flow[t][p[t]] += f;
  26. 	}
  27. }
  28. int Ed() {
  29. // Note That The Source Equal ( 1 ) And The Sink Equal ( 2 )
  30. 	int mf = 0;
  31. 	while (1) {
  32. 		memset(p, -1, sizeof p);
  33. 		f = 0;
  34. 		queue<int> q;q.push(1);
  35. 		while (!q.empty()) {
  36. 			int u = q.front();q.pop();
  37. 			if (u == 2)break;
  38. 			for (int i = 0; i < AdjList[u].size(); i++) {
  39. 				int v = AdjList[u][i];
  40. 				if (p[v] == -1 && Flow[u][v] > 0) {
  41. 					p[v] = u;
  42. 					q.push(v);
  43. 				}
  44. 			}
  45. 		}
  46. 		updatePath(2, (int)1e9);
  47. 		if (!f)break;
  48. 		mf += f;
  49. 	}
  50. 	return mf;
  51. }
  52.  
  53. int main(){
  54. 	//freopen("src.txt", "r", stdin);
  55. 	while (scanf("%d%d", &C, &P) && (C || P)) {
  56. 		AdjList.clear();
  57. 		AdjList.resize(C + P + 10);
  58. 		memset(Flow, 0, sizeof Flow);
  59. 		int total = 0;
  60. 		for (int i = 3 ;i <= C + 2; i++)
  61. 		{
  62. 			int z;scanf("%d", &z);
  63. 			AdjList[1].push_back(i);
  64. 			Flow[1][i] = z;
  65. 			total += z;
  66. 		}
  67. 		for (int i = 0 ; i < P ; i++) {
  68. 			int x;scanf("%d", &x);Flow[i + C + 3][2] = 1;AdjList[i + C + 3].push_back(2);
  69. 			while (x--) {
  70. 				int c;scanf("%d", &c);
  71. 				Flow[c + 2][i + C + 3] = 1;
  72. 				AdjList[c + 2].push_back(i + C + 3);
  73. 			}
  74. 		}
  75. 		if (Ed() == total) {
  76. 			printf("1\n");
  77. 			for (int i = 3; i <= C+2 ; i++) {
  78. 			bool c = 0;
  79. 				for (int j = 0 ; j < P ; j++) {
  80. 					if (Flow[j + C + 3][i]) {
  81. 						if (c)printf(" ");
  82. 						c = 1;
  83. 						printf("%d", j + 1);
  84. 					}
  85. 				}
  86. 				printf("\n");
  87. 			}
  88. 		}
  89. 		else {
  90. 			printf("0\n");
  91. 		}
  92.  
  93. 	}
  94.  
  95. 	return 0;
  96. }
Success #stdin #stdout 0s 12264KB
comments ()
stdin
copy 
3 15
3 3 4
2 1 2
1 3
1 3
1 3
1 3
3 1 2 3
2 2 3
2 1 3
1 2
1 2
2 1 2
2 1 3
2 1 2
1 1
3 1 2 3
3 15
7 3 4
2 1 2
1 1
1 2
1 2
1 3
3 1 2 3 2 2 3
2 2 3
1 2
1 2
2 2 3
2 2 3
2 1 2
1 1
3 1 2 3
0 0
stdout
copy 
1
1 6 8
7 9 10
2 3 4 5
0
https://ideone.com/hQ2EED
language:
C++ (gcc 8.3)
created:
9 years 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!