fork download
copy 
  1. #include <cstdio>
  2. #include <cstdlib>
  3. #include <cmath>
  4. #include <climits>
  5. #include <cfloat>
  6. #include <map>
  7. #include <utility>
  8. #include <set>
  9. #include <iostream>
  10. #include <memory>
  11. #include <string>
  12. #include <vector>
  13. #include <algorithm>
  14. #include <functional>
  15. #include <sstream>
  16. #include <complex>
  17. #include <stack>
  18. #include <queue>
  19. #include <numeric>
  20. #include <list>
  21. #include <time.h>
  22. #include <string.h>
  23. #include <assert.h>
  24. using namespace std;
  25. typedef long long ll;
  26.  
  27. template<class T> bool INRANGE(T x,T a,T b) { return a<=x&&x<=b; }
  28. #define NG (-1)
  29. #define BIG (123456789)
  30. #define BIGBIG (123456789123456789LL)
  31. #define SZ(a) ((int)(a).size()) 
  32.  
  33. // 最大流 Dinic O(EV^2)だけど、実際もっとはやい。
  34. class Dinic
  35. {
  36. public:
  37. 	Dinic(int input_maxv) : maxv(input_maxv)
  38. 	{
  39. 		G.resize(input_maxv);
  40. 		level.resize(input_maxv);
  41. 		iter.resize(input_maxv);
  42. 	}
  43.  
  44. 	void add_edge_both(int from, int to, ll cap)
  45. 	{
  46. 		if(cap>0)
  47. 		{
  48. 			const int rev_from	= SZ(G[from]);
  49. 			const int rev_to	= SZ(G[to]);
  50. 			G[from].push_back(edge(to,cap,rev_to));
  51. 			G[to].push_back(edge(from,cap,rev_from));
  52. 		}
  53. 	}
  54.  
  55. 	void add_edge(int from, int to, ll cap)
  56. 	{
  57. 		if(cap>0)
  58. 		{
  59. 			const int rev_from	= SZ(G[from]);
  60. 			const int rev_to	= SZ(G[to]);
  61. 			G[from].push_back(edge(to,cap,rev_to));
  62. 			G[to].push_back(edge(from,0,rev_from));
  63. 		}
  64. 	}
  65.  
  66. 	// sからtへの最大流を求める
  67. 	ll max_flow(int s, int t)
  68. 	{
  69. 		ll flow = 0;
  70. 		for(;;)
  71. 		{
  72. 			bfs(s);
  73. 			if(level[t]<0) break;
  74. 			fill(iter.begin(),iter.end(),0);
  75. 			ll f;
  76. 			while( (f=dfs(s,t,DINIC_INF))>0)
  77. 			{
  78. 				flow += f;
  79. 			}
  80. 		}
  81.  
  82. 		return flow;
  83. 	}
  84.  
  85. 	//  ノードsから辿れる範囲を求める（これ以上流せないところcap=0は、リンクがなくなる）
  86. 	// （流し終わったあとsourceからたどれる範囲が、最小カット時のs側。たどれない法がt側。その境界がカットするところ。）
  87. 	vector <bool> get_nodes_in_group(int s)
  88. 	{
  89. 		vector <bool> ret(maxv);
  90.  
  91. 		queue<int> que;
  92. 		que.push(s);
  93. 		while(!que.empty())
  94. 		{
  95. 			int v = que.front();
  96. 			que.pop();
  97. 			ret[v]=true;
  98.  
  99. 			for(int i=0;i<SZ(G[v]);i++)
  100. 			{
  101. 				edge &e = G[v][i];
  102. 				if(e.cap>0 && !ret[e.to])
  103. 				{
  104. 					que.push(e.to);
  105. 				}
  106. 			}
  107. 		}
  108. 		return ret;
  109. 	}
  110.  
  111. 	void disp()
  112. 	{
  113. 		for (int v = 0; v < maxv; v++)
  114. 		{
  115. 			printf("%d:",v);
  116. 			for(int i=0;i<SZ(G[v]);i++)
  117. 			{
  118. 				if(G[v][i].init_cap>0)
  119. 				{
  120. 					printf("->%d(%lld),",G[v][i].to,G[v][i].init_cap);
  121. 				}
  122. 			}
  123. 			printf("\n");
  124. 		}
  125. 	}
  126.  
  127. private:
  128. 	// sからの最短距離をBFSで計算する
  129. 	void bfs(int s)
  130. 	{
  131. 		fill(level.begin(),level.end(),NG);
  132. 		queue<int> que;
  133. 		level[s]=0;
  134. 		que.push(s);
  135. 		while(!que.empty())
  136. 		{
  137. 			int v = que.front();
  138. 			que.pop();
  139. 			for(int i=0;i<SZ(G[v]);i++)
  140. 			{
  141. 				edge &e = G[v][i];
  142. 				if(e.cap>0 && level[e.to]<0)
  143. 				{
  144. 					level[e.to] = level[v] + 1;
  145. 					que.push(e.to);
  146. 				}
  147. 			}
  148. 		}
  149. 	}
  150.  
  151. 	// 増加パスをDFSで探す
  152. 	ll dfs(int v, int t, ll f)
  153. 	{
  154. 		if(v==t) return f;
  155. 		for (int &i=iter[v];i<SZ(G[v]);i++)
  156. 		{
  157. 			edge& e = G[v][i];
  158. 			if(e.cap>0 && level[v]<level[e.to])
  159. 			{
  160. 				ll d = dfs(e.to, t, min(f, e.cap));
  161. 				if(d>0)
  162. 				{
  163. 					e.cap -= d;
  164. 					G[e.to][e.rev].cap += d;
  165. 					return d;
  166. 				}
  167. 			}
  168. 		}
  169. 		return 0;
  170. 	}
  171.  
  172. 	static const ll DINIC_INF = LLONG_MAX; // 容量をllにしたいときは、ここも変える
  173.  
  174. 	struct edge 
  175. 	{
  176. 		edge(int input_to, ll input_cap, int input_rev) : to(input_to), cap(input_cap), rev(input_rev), init_cap(input_cap) {}
  177. 		int to;		// 行先
  178. 		ll cap;	// 容量
  179. 		int rev;	// 逆辺
  180. 		ll init_cap; // 初期容量（デバッグ用）
  181. 	};
  182.  
  183. 	int	maxv;
  184. 	vector < vector <edge> > G;	// グラフの隣接リスト
  185. 	vector < int > level;		// sからの距離
  186. 	vector < int > iter;		// どこまで調べ終わったか
  187. };
  188.  
  189.  
  190. class RabbitWorking {
  191. public:
  192.  
  193.  
  194. 	bool ok(ll a, ll b, const vector <string>& profit)
  195. 	{
  196. 		const int N = SZ(profit);
  197. 		const int S = N+N*(N-1)/2;
  198. 		const int T = S+1;
  199. 		const int V = T+1;
  200. 		Dinic*	dinic = new Dinic(V);
  201.  
  202. 		ll ret = 0;
  203. 		int v = 0;
  204. 		for (int i = 0; i < N; i++)
  205. 		{
  206. 			dinic->add_edge(S,i,199*a);
  207. 			v++;
  208. 		}
  209.  
  210. 		for (int i = 0; i < N; i++)
  211. 		{
  212. 			for (int j = i+1; j < N; j++)
  213. 			{
  214. 				ll p = profit[i][j]-'0';
  215. 				ll cost = b*p+2*a;
  216. 				ret += cost;
  217. 				dinic->add_edge(v,T,cost);
  218. 				dinic->add_edge(i,v,BIGBIG);
  219. 				dinic->add_edge(j,v,BIGBIG);
  220. 				v++;
  221. 			}
  222. 		}
  223.  
  224. 		ret -= dinic->max_flow(S,T);
  225. 		delete dinic;
  226.  
  227. 		return ret>0;
  228. 	}
  229.  
  230. 	double getMaximum(vector <string> profit) {
  231.  
  232. 		ll b = (ll)1e12;
  233. 		ll lo = 0;
  234. 		ll hi = (ll)b*100;
  235.  
  236. 		while(lo<hi)
  237. 		{
  238. 			ll mid = lo+(hi-lo)/2LL;
  239. 			if(!ok(mid,b,profit))
  240. 			{
  241. 				hi=mid;
  242. 			}
  243. 			else
  244. 			{
  245. 				lo=mid+1;
  246. 			}
  247. 		}
  248.  
  249. 		return (double)lo/b;
  250. 	}
  251.  
  252. private:
  253. 	template <typename T> string print_array(const vector<T> &V) { ostringstream os; os << "{ "; for (typename vector<T>::const_iterator iter = V.begin(); iter != V.end(); ++iter) os << '\"' << *iter << "\","; os << " }"; return os.str(); }
  254.  
  255. 	void verify_case(int Case, const double &Expected, const double &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
  256.  
  257. public:
  258. 	void run_test(int Case) { 
  259. 		int n = 0;
  260.  
  261. 		// test_case_0
  262. 		if ((Case == -1) || (Case == n)){
  263. 			string Arr0[] = { "071", 
  264.   "702", 
  265.   "120" }
  266. ;
  267. 			double Arg1 = 0.017676767676767676;
  268.  
  269. 			vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0])));
  270. 			verify_case(n, Arg1, getMaximum(Arg0));
  271. 		}
  272. 		n++;
  273.  
  274. 		// test_case_1
  275. 		if ((Case == -1) || (Case == n)){
  276. 			string Arr0[] = { "061", 
  277.   "602", 
  278.   "120" }
  279. ;
  280. 			double Arg1 = 0.015228426395939087;
  281.  
  282. 			vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0])));
  283. 			verify_case(n, Arg1, getMaximum(Arg0));
  284. 		}
  285. 		n++;
  286.  
  287. 		// test_case_2
  288. 		if ((Case == -1) || (Case == n)){
  289. 			string Arr0[] = { "0" }
  290. ;
  291. 			double Arg1 = 0.0;
  292.  
  293. 			vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0])));
  294. 			verify_case(n, Arg1, getMaximum(Arg0));
  295. 		}
  296. 		n++;
  297.  
  298. 		// test_case_3
  299. 		if ((Case == -1) || (Case == n)){
  300. 			string Arr0[] = { "013040", 
  301.   "100010", 
  302.   "300060", 
  303.   "000008", 
  304.   "416000", 
  305.   "000800" }
  306. ;
  307. 			double Arg1 = 0.021996615905245348;
  308.  
  309. 			vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0])));
  310. 			verify_case(n, Arg1, getMaximum(Arg0));
  311. 		}
  312. 		n++;
  313.  
  314. 		// test_case_4
  315. 		if ((Case == -1) || (Case == n)){
  316. 			string Arr0[] = { "06390061", 
  317.   "60960062", 
  318.   "39090270", 
  319.   "96900262", 
  320.   "00000212", 
  321.   "00222026", 
  322.   "66761201", 
  323.   "12022610" }
  324. ;
  325. 			double Arg1 = 0.06871794871794872;
  326.  
  327. 			vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0])));
  328. 			verify_case(n, Arg1, getMaximum(Arg0));
  329. 		}
  330. 		n++;
  331.  
  332. 	}
  333.  
  334. };
  335.  
  336. int main() {
  337. 	RabbitWorking* ___test = new RabbitWorking();
  338. 	___test->run_test(-1);
  339. 	delete ___test;
  340. }
  341.  
  342.  
Success #stdin #stdout #stderr 0s 3492KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Test Case #0...FAILED
	Expected: "0.0176768"
	Received: "0.0176768"
Test Case #1...FAILED
	Expected: "0.0152284"
	Received: "0.0152284"
Test Case #2...PASSED
Test Case #3...FAILED
	Expected: "0.0219966"
	Received: "0.0219966"
Test Case #4...FAILED
	Expected: "0.0687179"
	Received: "0.0687179"
https://ideone.com/8QljRJ
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!