fork 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];
  12. int n, m, k, g[N][N], vis[N], par[N], qu[N], vs;
  13.  
  14. void addEdge(int u, int v, int c) {
  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] += c;
  20. }
  21.  
  22. bool BFS(int src, int sink) {
  23. 	int s = 0, e = 0, lev = 0;
  24. 	qu[e++] = src;
  25. 	vis[src] = ++vs;
  26. 	while (s < e && lev < k * 2) {
  27. 		int siz = e - s;
  28. 		while (siz--) {
  29. 			int v = qu[s++];
  30. 			for (size_t i = 0; i < adj[v].size(); ++i) {
  31. 				int u = adj[v][i];
  32. 				if (vis[u] == vs || !g[v][u])
  33. 					continue;
  34. 				vis[u] = vs;
  35. 				par[u] = v;
  36. 				qu[e++] = u;
  37. 				if (u == sink)
  38. 					return true;
  39. 			}
  40. 		}
  41. 		++lev;
  42. 	}
  43. 	return false;
  44. }
  45.  
  46. int maxFlow(int src, int sink) {
  47. 	int flow = 0;
  48. 	while (BFS(src, sink)) {
  49. 		++flow;
  50. 		for (int u = sink; u != src; u = par[u]) {
  51. 			int v = par[u];
  52. 			++g[u][v];
  53. 			--g[v][u];
  54. 		}
  55. 	}
  56. 	return flow;
  57. }
  58.  
  59. int main(int argc, char **argv) {
  60. //	freopen("a", "r", stdin);
  61. //	freopen("b", "w", stdout);
  62. 	while (scanf("%d%d%d", &n, &m, &k) && n) {
  63. 		for (int i = 0; i < n * 2; ++i) {
  64. 			adj[i].clear();
  65. 			for (int j = i; j < n * 2; ++j)
  66. 				g[i][j] = g[j][i] = 0;
  67. 		}
  68. 		addEdge(0, n, 1e9);
  69. 		for (int i = 1; i < n; ++i)
  70. 			addEdge(i, i + n, 1);
  71. 		while (m--) {
  72. 			int u, v;
  73. 			scanf("%d%d", &u, &v);
  74. 			--u;
  75. 			--v;
  76. 			addEdge(u + n, v, 1);
  77. 		}
  78. 		if (n == 1)
  79. 			printf("%d\n", m);
  80. 		else
  81. 			printf("%d\n", maxFlow(0, n - 1));
  82. 	}
  83. 	return 0;
  84. }
Success #stdin #stdout 0s 3316KB
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/h93j8q
language:
C++14 (gcc 8.3)
created:
8 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!