fork download
copy 
  1. #include <stdio.h>
  2. #include <cstdio>
  3. #include <cstdlib>
  4. #include <cmath>
  5. #include <climits>
  6. #include <cfloat>
  7. #include <map>
  8. #include <utility>
  9. #include <set>
  10. #include <iostream>
  11. #include <memory>
  12. #include <string>
  13. #include <vector>
  14. #include <algorithm>
  15. #include <functional>
  16. #include <sstream>
  17. #include <complex>
  18. #include <stack>
  19. #include <queue>
  20. #include <numeric>
  21. #include <stdio.h>
  22. #include <string.h>
  23. #include <assert.h>
  24.  
  25. using namespace std;
  26. static const double EPS = 1e-9;
  27. int ROUND(double x) { return (int)(x+0.5); }
  28. bool ISINT(double x) { return fabs(ROUND(x)-x)<=EPS; }
  29. bool ISEQUAL(double x,double y) { return fabs(x-y)<=EPS*max(1.0,max(fabs(x),fabs(y))); }
  30. double SQSUM(double x,double y) { return x*x+y*y; }
  31. template<class T> bool INRANGE(T x,T a,T b) { return a<=x&&x<=b; }
  32. #define PI  (acos(-1))
  33. #define ARRAY_NUM(a) (sizeof(a)/sizeof(a[0])) 
  34. #define NG (-1)
  35. #define BIG (987654321)
  36. #define SZ(a) ((int)((a).size()))
  37. #define SQ(a) ((a)*(a))
  38. typedef long long ll;
  39. typedef unsigned long long ull;
  40.  
  41. #define FOR(v,i) for(__typeof((v).begin())i=(v).begin();i!=(v).end();++i)
  42. // BEGIN CUT HERE
  43. #undef FOR
  44. #define FOR(v,i) for(auto i=(v).begin();i!=(v).end();++i)
  45. // END CUT HERE
  46.  
  47. // 最大流 Dinic O(EV^2)だけど、実際もっとはやい。
  48. class Dinic
  49. {
  50. public:
  51. 	Dinic(int input_maxv) : maxv(input_maxv)
  52. 	{
  53. 		G.resize(input_maxv);
  54. 		level.resize(input_maxv);
  55. 		iter.resize(input_maxv);
  56. 	}
  57.  
  58. 	void add_edge_both(int from, int to, int cap)
  59. 	{
  60. 		const int rev_from  = SZ(G[from]);
  61. 		const int rev_to    = SZ(G[to]);
  62. 		G[from].push_back(edge(to,cap,rev_to));
  63. 		G[to].push_back(edge(from,cap,rev_from));
  64. 	}
  65.  
  66. 	void add_edge(int from, int to, int cap)
  67. 	{
  68. 		const int rev_from  = SZ(G[from]);
  69. 		const int rev_to    = SZ(G[to]);
  70. 		G[from].push_back(edge(to,cap,rev_to));
  71. 		G[to].push_back(edge(from,0,rev_from));
  72. 	}
  73.  
  74. 	// sからtへの最大流を求める
  75. 	int max_flow(int s, int t)
  76. 	{
  77. 		int flow = 0;
  78. 		for(;;)
  79. 		{
  80. 			bfs(s);
  81. 			if(level[t]<0) break;
  82. 			fill(iter.begin(),iter.end(),0);
  83. 			int f;
  84. 			while( (f=dfs(s,t,DINIC_INF))>0)
  85. 			{
  86. 				flow += f;
  87. 			}
  88. 		}
  89.  
  90. 		return flow;
  91. 	}
  92.  
  93. 	//  ノードsから辿れる範囲を求める（これ以上流せないところcap=0は、リンクがなくなる）
  94. 	// （流し終わったあとsourceからたどれる範囲が、最小カット時のs側。たどれない範囲がt側。その境界がカットするところ。）
  95. 	vector <bool> get_nodes_in_group(int s)
  96. 	{
  97. 		vector <bool> ret(maxv);
  98.  
  99. 		queue<int> que;
  100. 		que.push(s);
  101. 		while(!que.empty())
  102. 		{
  103. 			int v = que.front();
  104. 			que.pop();
  105. 			ret[v]=true;
  106.  
  107. 			for(int i=0;i<SZ(G[v]);i++)
  108. 			{
  109. 				edge &e = G[v][i];
  110. 				if(e.cap>0 && !ret[e.to])
  111. 				{
  112. 					que.push(e.to);
  113. 				}
  114. 			}
  115. 		}
  116. 		return ret;
  117. 	}
  118.  
  119. 	void disp()
  120. 	{
  121. 		for (int v = 0; v < maxv; v++)
  122. 		{
  123. 			printf("%d:",v);
  124. 			for(int i=0;i<SZ(G[v]);i++)
  125. 			{
  126. 				if(G[v][i].init_cap>0)
  127. 				{
  128. 					printf("->%d(%d),",G[v][i].to,G[v][i].init_cap);
  129. 				}
  130. 			}
  131. 			printf("\n");
  132. 		}
  133. 	}
  134.  
  135. private:
  136. 	// sからの最短距離をBFSで計算する
  137. 	void bfs(int s)
  138. 	{
  139. 		fill(level.begin(),level.end(),NG);
  140. 		queue<int> que;
  141. 		level[s]=0;
  142. 		que.push(s);
  143. 		while(!que.empty())
  144. 		{
  145. 			int v = que.front();
  146. 			que.pop();
  147. 			for(int i=0;i<SZ(G[v]);i++)
  148. 			{
  149. 				edge &e = G[v][i];
  150. 				if(e.cap>0 && level[e.to]<0)
  151. 				{
  152. 					level[e.to] = level[v] + 1;
  153. 					que.push(e.to);
  154. 				}
  155. 			}
  156. 		}
  157. 	}
  158.  
  159. 	// 増加パスをDFSで探す
  160. 	int dfs(int v, int t, int f)
  161. 	{
  162. 		if(v==t) return f;
  163. 		for (int &i=iter[v];i<SZ(G[v]);i++)
  164. 		{
  165. 			edge& e = G[v][i];
  166. 			if(e.cap>0 && level[v]<level[e.to])
  167. 			{
  168. 				int d = dfs(e.to, t, min(f, e.cap));
  169. 				if(d>0)
  170. 				{
  171. 					e.cap -= d;
  172. 					G[e.to][e.rev].cap += d;
  173. 					return d;
  174. 				}
  175. 			}
  176. 		}
  177. 		return 0;
  178. 	}
  179.  
  180. 	static const int DINIC_INF = INT_MAX; // 容量をllにしたいときは、ここも変える
  181.  
  182. 	struct edge 
  183. 	{
  184. 		edge(int input_to, int input_cap, int input_rev) : to(input_to), cap(input_cap), rev(input_rev), init_cap(input_cap) {}
  185. 		int to;     // 行先
  186. 		int cap;    // 容量
  187. 		int rev;    // 逆辺
  188. 		int init_cap; // 初期容量（デバッグ用）
  189. 	};
  190.  
  191. 	int maxv;
  192. 	vector < vector <edge> > G; // グラフの隣接リスト
  193. 	vector < int > level;     // sからの距離
  194. 	vector < int > iter;      // どこまで調べ終わったか
  195.  
  196. };
  197.  
  198. int main()
  199. {
  200. 	int n, penalty;
  201. 	cin >> n >> penalty;
  202.  
  203. 	const int S = n;
  204. 	const int T = S+1;
  205. 	const int V = T+1;
  206.  
  207. 	{
  208. 		Dinic* dinic = new Dinic(V);
  209. 		for (int i = 0; i < n; i++)
  210. 		{
  211. 			int moyasu,umeru;
  212. 			cin >> moyasu >> umeru;
  213. 			dinic->add_edge(S,i,moyasu);
  214. 			dinic->add_edge(i,T,umeru);
  215. 		}
  216. 		dinic->add_edge(1,0,penalty);
  217.  
  218. 		int answer = dinic->max_flow(S,T);
  219. 		printf("%d\n",answer);
  220.  
  221. 		delete dinic;
  222. 	}
  223.  
  224. 	return 0;
  225. }
  226.  
Success #stdin #stdout 0s 3444KB
comments (?)
stdin
copy 
2 300
20 50
100 20
stdout
copy 
70
https://ideone.com/OlgYjD
language:
C++ (gcc 8.3)
created:
10 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!