fork download
  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
stdin
5 7 3 
1 3 
3 4 
4 5 
1 2 
2 5 
1 4 
4 5 
0 0 0
stdout
2