fork download
copy 
  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
comments (?)
stdin
copy 
9 9
0 1
1 2
2 0
3 4
4 3
5 6
6 7
7 8
8 5
stdout
copy 
Standard output is empty
https://ideone.com/Y2YdTa
language:
C++ (gcc 8.3)
created:
7 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!