fork(1) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /*
  5.  * You got a dream, you gotta protect it.
  6.  */
  7.  
  8. typedef long long ll;
  9.  
  10. const int N = 100;
  11. vector<int> adj[N], G[50];
  12. int g[N][N], vis[N], qu[N], par[N], vs;
  13.  
  14. void addEdge(int u, int v) {
  15. 	if (!g[u][v] && !g[v][u]) {
  16. 		adj[u].push_back(v);
  17. 		adj[v].push_back(u);
  18. 	}
  19. 	++g[u][v];
  20. }
  21.  
  22. bool BFS(int src, int sink) {
  23. 	int s = 0, e = 0;
  24. 	qu[e++] = src;
  25. 	vis[src] = ++vs;
  26. 	while (s < e) {
  27. 		int v = qu[s++];
  28. 		for (size_t i = 0; i < adj[v].size(); ++i) {
  29. 			int u = adj[v][i];
  30. 			if (vis[u] == vs || !g[v][u])
  31. 				continue;
  32. 			vis[u] = vs;
  33. 			par[u] = v;
  34. 			qu[e++] = u;
  35. 			if (u == sink)
  36. 				return true;
  37. 		}
  38. 	}
  39. 	return false;
  40. }
  41.  
  42. int maxFlow(int src, int sink) {
  43. 	int flow = 0;
  44. 	while (BFS(src, sink)) {
  45. 		++flow;
  46. 		for (int u = sink; u != src; u = par[u]) {
  47. 			int v = par[u];
  48. 			++g[u][v];
  49. 			--g[v][u];
  50. 		}
  51. 	}
  52. 	return flow;
  53. }
  54.  
  55. int main(int argc, char **argv) {
  56. //	freopen("a", "r", stdin);
  57. //	freopen("b", "w", stdout);
  58. 	int n, m, k;
  59. 	while (scanf("%d%d%d", &n, &m, &k) && n) {
  60. 		for (int i = 0; i < n; ++i)
  61. 			G[i].clear();
  62. 		while (m--) {
  63. 			int u, v;
  64. 			scanf("%d%d", &u, &v);
  65. 			--u;
  66. 			--v;
  67. 			G[u].push_back(v);
  68. 		}
  69. 		int s = 0, e = 0, lev = 0;
  70. 		qu[e++] = 0;
  71. 		vis[0] = ++vs;
  72. 		while (s < e && lev < k) {
  73. 			int siz = e - s;
  74. 			while (siz--) {
  75. 				int v = qu[s++];
  76. 				for (size_t i = 0; i < G[v].size(); ++i) {
  77. 					int u = G[v][i];
  78. 					if (vis[u] == vs)
  79. 						continue;
  80. 					if (lev + 1 < k || (lev + 1 == k && u == n - 1))
  81. 						vis[u] = vs, qu[e++] = u;
  82. 				}
  83. 			}
  84. 			++lev;
  85. 		}
  86. 		for (int i = 0; i < n * 2; ++i) {
  87. 			adj[i].clear();
  88. 			for (int j = i; j < n * 2; ++j)
  89. 				g[i][j] = g[j][i] = 0;
  90. 		}
  91. 		for (int i = 0; i < e; ++i) {
  92. 			int u = qu[i];
  93. 			if (u && u != n - 1)
  94. 				addEdge(u, u + n);
  95. 			for (size_t j = 0; j < G[u].size(); ++j)
  96. 				if (u)
  97. 					addEdge(u + n, G[u][j]);
  98. 				else
  99. 					addEdge(u, G[u][j]);
  100. 		}
  101. 		printf("%d\n", maxFlow(0, n - 1));
  102. 	}
  103. 	return 0;
  104. }
Success #stdin #stdout 0s 3276KB
comments (?)
stdin
copy 
5 7 3 
1 3 
3 4 
4 5 
1 2 
2 5 
1 4 
4 5 
0 0 0
stdout
copy 
2
https://ideone.com/RhqyN8
language:
C++14 (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!