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. while(true) {
  109. int augmenting = find_blocking_flow(source, MAX_CAPACITY);
  110. if (augmenting > 0)
  111. {
  112. answer += augmenting;
  113. }
  114. else
  115. {
  116. break;
  117. }
  118. }
  119. }
  120. return answer;
  121. }
  122. };
  123.  
  124. Graph::edge_t Graph::edges[2*Graph::MAX_EDGES] = {};
  125. vector<int> Graph::out_edges[Graph::MAX_VERTICES] = {};
  126. int Graph::first[Graph::MAX_VERTICES] = {};
  127. int Graph::dist[Graph::MAX_VERTICES] = {};
  128.  
  129. void _1711()
  130. {
  131. int n, m;
  132. scanf("%d%d", &n, &m);
  133. Graph graph(n, 0, n-1);
  134. for (int i = 0; i < m; ++i)
  135. {
  136. int a, b, c;
  137. scanf("%d%d%d", &a, &b, &c);
  138. --a; --b;
  139. graph.add_edge(a, b, c);
  140. }
  141. printf("%lld\n", graph.max_flow());
  142. exit(0);
  143. }
  144.  
  145. int main()
  146. {
  147. int n, m;
  148. //_1711();
  149. while (2 == scanf("%d%d", &n, &m))
  150. {
  151. Graph graph(2*n + 2, 0, 2*n + 1);
  152. for (int person = 1; person <= n; ++person)
  153. {
  154. graph.add_edge(0, person, 1);
  155. graph.add_edge(person+n, 2*n+1, 1);
  156. }
  157. for (int interest = 0; interest < m; ++interest)
  158. {
  159. int a, b;
  160. scanf("%d%d", &a, &b);
  161. ++a; ++b;
  162. graph.add_edge(a, n + b, 1);
  163. }
  164. if (graph.max_flow() == n)
  165. {
  166. printf("YES\n");
  167. }
  168. else
  169. {
  170. printf("NO\n");
  171. }
  172. }
  173.  
  174.  
  175. return 0;
  176. }
  177.  
Success #stdin #stdout 0s 4824KB
stdin
Standard input is empty
stdout
Standard output is empty