fork download
  1. #include <cstdio>
  2. #include <list>
  3. #include <vector>
  4. #include <queue>
  5. #include <cstring>
  6. #include <cstdlib>
  7.  
  8. using namespace std;
  9.  
  10. const int MAXN = 10000;
  11. const int MAXM = 20000;
  12.  
  13. class Graph
  14. {
  15. static const int MAX_VERTICES = MAXN * 2 + 2;
  16. static const int MAX_CAPACITY = (int)1;
  17. static const int MAX_EDGES = MAXM + MAXN * 2;
  18.  
  19. struct edge_t
  20. {
  21. int to;
  22. int flow, capacity;
  23. int residual_capacity()const { return capacity - flow; }
  24. };
  25.  
  26. static edge_t edges[2*MAX_EDGES];
  27. int edges_size;
  28. static vector<int> out_edges[MAX_VERTICES];
  29. static int first[MAX_VERTICES];
  30. static int dist[MAX_VERTICES];
  31. int source, sink, vertices;
  32.  
  33. bool build_level_graph()
  34. {
  35. memset(dist, -1, sizeof(*dist) * vertices);
  36. static int q[MAX_VERTICES];
  37. int q_head = 0, q_tail = 0;
  38. dist[source] = 0;
  39. q[q_tail++] = source;
  40.  
  41. while (q_head < q_tail && dist[sink] == -1)
  42. {
  43. int vertex = q[q_head++];
  44. for (int edge : out_edges[vertex])
  45. {
  46. const edge_t &forward = edges[edge];
  47. if (dist[forward.to] == -1 && forward.residual_capacity() > 0)
  48. {
  49. q[q_tail++] = forward.to;
  50. dist[forward.to] = dist[vertex] + 1;
  51. }
  52. }
  53. }
  54.  
  55. return dist[sink] != -1;
  56. }
  57.  
  58. int find_blocking_flow(int vertex, int flow)
  59. {
  60. if (flow == 0)
  61. {
  62. return 0;
  63. }
  64. if (vertex == sink)
  65. {
  66. return flow;
  67. }
  68.  
  69. for (; first[vertex] < (int)out_edges[vertex].size(); ++first[vertex])
  70. {
  71. edge_t &forward = edges[out_edges[vertex][first[vertex]]];
  72. if (dist[forward.to] == dist[vertex] + 1)
  73. {
  74. int augumenting = find_blocking_flow(forward.to, min(flow, forward.residual_capacity()));
  75. if (augumenting > 0)
  76. {
  77. edge_t &backward = edges[out_edges[vertex][first[vertex]] ^ 1];
  78. forward.flow += augumenting;
  79. backward.flow -= augumenting;
  80. return augumenting;
  81. }
  82. }
  83. }
  84.  
  85.  
  86. return false;
  87. }
  88.  
  89. public:
  90. Graph(int vertices, int source, int sink) : vertices(vertices), source(source), sink(sink), edges_size(0)
  91. {}
  92. void add_edge(int from, int to, int capacity)
  93. {
  94. edge_t forward = { to, 0, capacity };
  95. edge_t backward = { from, 0, 0 };
  96. out_edges[from].push_back(edges_size);
  97. edges[edges_size++] = forward;
  98. out_edges[to].push_back(edges_size);
  99. edges[edges_size++] = backward;
  100. }
  101.  
  102. long long max_flow()
  103. {
  104. long long answer = 0;
  105. for (int i = 0; build_level_graph(); ++i)
  106. {
  107. memset(first, 0, sizeof(*first)*vertices);
  108. int augmenting = find_blocking_flow(source, MAX_CAPACITY);
  109. if (augmenting > 0)
  110. {
  111. answer += augmenting;
  112. }
  113. else
  114. {
  115. break;
  116. }
  117. }
  118. return answer;
  119. }
  120. };
  121.  
  122. Graph::edge_t Graph::edges[2*Graph::MAX_EDGES] = {};
  123. vector<int> Graph::out_edges[Graph::MAX_VERTICES] = {};
  124. int Graph::first[Graph::MAX_VERTICES] = {};
  125. int Graph::dist[Graph::MAX_VERTICES] = {};
  126.  
  127. void _1711()
  128. {
  129. int n, m;
  130. scanf("%d%d", &n, &m);
  131. Graph graph(n, 0, n-1);
  132. for (int i = 0; i < m; ++i)
  133. {
  134. int a, b, c;
  135. scanf("%d%d%d", &a, &b, &c);
  136. --a; --b;
  137. graph.add_edge(a, b, c);
  138. }
  139. printf("%lld\n", graph.max_flow());
  140. exit(0);
  141. }
  142.  
  143. int main()
  144. {
  145. int n, m;
  146. //_1711();
  147. while (2 == scanf("%d%d", &n, &m))
  148. {
  149. Graph graph(2*n + 2, 0, 2*n + 1);
  150. for (int person = 1; person <= n; ++person)
  151. {
  152. graph.add_edge(0, person, 1);
  153. graph.add_edge(person+n, 2*n+1, 1);
  154. }
  155. for (int interest = 0; interest < m; ++interest)
  156. {
  157. int a, b;
  158. scanf("%d%d", &a, &b);
  159. ++a; ++b;
  160. graph.add_edge(a, n + b, 1);
  161. }
  162. if (graph.max_flow() == n)
  163. {
  164. printf("YES\n");
  165. }
  166. else
  167. {
  168. printf("NO\n");
  169. }
  170. }
  171.  
  172.  
  173. return 0;
  174. }
Time limit exceeded #stdin #stdout 5s 4872KB
stdin
9 9
0 1
1 2
2 0
3 4
4 3
5 6
6 7
7 8
8 5
stdout
Standard output is empty