fork download
copy 
  1. #include <cstring>
  2. #include <vector>
  3. using namespace std;
  4. class Dinic {
  5.     static const int MAXN = 1000, INF = 1e9;
  6. 	private:
  7. 		struct edge {
  8. 			int a, b, cap, flow;
  9. 		};
  10. 		int n, s, t, d[MAXN], ptr[MAXN], q[MAXN];
  11. 		vector<edge> e;
  12. 		vector<int> g[MAXN];
  13. 	public:
  14. 		//takes in number of nodes source and sink
  15. 		Dinic(int a, int b, int c): n(a), s(b), t(c) {	}
  16. 		void add_edge (int a, int b, int cap) {
  17. 			edge e1 = { a, b, cap, 0 };
  18. 			edge e2 = { b, a, 0, 0 };
  19. 			g[a].push_back ((int) e.size());
  20. 			e.push_back (e1);
  21. 			g[b].push_back ((int) e.size());
  22. 			e.push_back (e2);
  23. 		}
  24. 		bool bfs() {
  25. 			int qh=0, qt=0;
  26. 			q[qt++] = s;
  27. 			memset (d, -1, n * sizeof d[0]);
  28. 			d[s] = 0;
  29. 			while (qh < qt && d[t] == -1) {
  30. 				int v = q[qh++];
  31. 				for (size_t i=0; i<g[v].size(); ++i) {
  32. 					int id = g[v][i],
  33. 						to = e[id].b;
  34. 					if (d[to] == -1 && e[id].flow < e[id].cap) {
  35. 						q[qt++] = to;
  36. 						d[to] = d[v] + 1;
  37. 					}
  38. 				}
  39. 			}
  40. 			return d[t] != -1;
  41. 		}
  42. 		int dfs (int v, int flow) {
  43. 			if (!flow)  return 0;
  44. 			if (v == t)  return flow;
  45. 			for (; ptr[v]<(int)g[v].size(); ++ptr[v]) {
  46. 				int id = g[v][ptr[v]],
  47. 					to = e[id].b;
  48. 				if (d[to] != d[v] + 1)  continue;
  49. 				int pushed = dfs (to, min (flow, e[id].cap - e[id].flow));
  50. 				if (pushed) {
  51. 					e[id].flow += pushed;
  52. 					e[id^1].flow -= pushed;
  53. 					return pushed;
  54. 				}
  55. 			}
  56. 			return 0;
  57. 		}
  58. 		int dinic() {
  59. 			int flow = 0;
  60. 			for (;;) {
  61. 				if (!bfs())  break;
  62. 				memset (ptr, 0, n * sizeof ptr[0]);
  63. 				while (int pushed = dfs (s, INF))
  64. 					flow += pushed;
  65. 			}
  66. 			return flow;
  67. 		}
  68. };
  69.  
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/usr/lib/gcc/i586-linux-gnu/5/../../../i386-linux-gnu/crt1.o: In function `_start':
(.text+0x18): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/cieUlL
language:
C++14 (gcc 8.3)
created:
8 years ago
visibility:
secret

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!