fork download
copy 
  1. #define pb push_back
  2. #define mp make_pair
  3. #define _(a,b) memset((a),(b),sizeof(a))
  4. #define sz(a) (int)(a).size()
  5.  
  6. const int maxn = 60100;
  7. const int INF = 1000000000;
  8.  
  9. struct Edge
  10. {
  11.     int a, b, id, cap, flow, cost;
  12. };
  13.  
  14. vector<int> g[maxn];
  15. vector<Edge> e;
  16. int S, T;
  17. int d[maxn], pot[maxn], last[maxn];
  18. set<pair<int, int> > q;
  19.  
  20. void adde(int a, int b, int cap, int cost)
  21. {
  22. 	Edge t;
  23. 	t.a = a;
  24. 	t.b = b;
  25. 	t.id = sz(e);
  26. 	t.cap = cap;
  27. 	t.flow = 0;
  28. 	t.cost = cost;
  29. 	e.pb(t);
  30. 	g[t.a].pb(t.id);
  31.  
  32. 	t.id++;
  33. 	swap(t.a, t.b);
  34. 	t.cap = 0;
  35. 	t.cost = -cost;
  36. 	e.pb(t);
  37. 	g[t.a].pb(t.id);
  38. }
  39.  
  40. void update(int id, int nd, int lst)
  41. {
  42. 	if (d[id] > nd)
  43. 	{
  44. 		q.erase(mp(d[id], id));
  45. 		d[id] = nd;
  46. 		last[id] = lst;
  47. 		q.insert(mp(nd, id));
  48. 	}
  49. }
  50.  
  51. bool dij()
  52. {
  53. 	_(d, 127);
  54. 	update(S, 0, -1);
  55. 	while (!q.empty())
  56. 	{
  57. 		int id = q.begin()->second;
  58. 		q.erase(q.begin());
  59. 		for (int i = 0; i < sz(g[id]); i++)
  60. 		{
  61. 			Edge &t = e[g[id][i]];
  62. 			if (t.flow < t.cap)
  63. 				update(t.b, d[t.a] + pot[t.a] - pot[t.b] + t.cost, t.id);
  64. 		}
  65. 	}
  66. 	for (int i = 0; i < maxn; i++)
  67. 	{
  68. 		if (d[i] < INF)
  69. 			pot[i] += d[i];
  70. 	}
  71. 	return d[T] < INF;
  72. }
  73.  
  74. void augm()
  75. {
  76. 	int id = T, mn = INF;
  77. 	while (id != S)
  78. 	{
  79. 		Edge &t = e[last[id]];
  80. 		mn = min(mn, t.cap - t.flow);
  81. 		id = t.a;
  82. 	}
  83. 	id = T;
  84. 	while (id != S)
  85. 	{
  86. 		Edge &t = e[last[id]];
  87. 		t.flow += mn;
  88. 		e[t.id ^ 1].flow -= mn;
  89. 		id = t.a;
  90. 	}
  91. }
  92.  
  93. int flow()
  94. {
  95. 	while (dij())
  96. 		augm();
  97. 	int ret = 0;
  98. 	for (int i = 0; i < sz(e); i += 2)
  99. 		ret += e[i].flow * e[i].cost;
  100. 	return ret;
  101. }
  102.  
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/61IrEa
language:
C++ (gcc 8.3)
created:
11 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!