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 (987654321)
  30. #define SZ(a) ((int)(a).size()) 
  31.  
  32. // 最大流 Dinic O(EV^2)だけど、実際もっとはやい。
  33. class Dinic
  34. {
  35. public:
  36. 	Dinic(int input_maxv) : maxv(input_maxv)
  37. 	{
  38. 		G.resize(input_maxv);
  39. 		level.resize(input_maxv);
  40. 		iter.resize(input_maxv);
  41. 	}
  42.  
  43. 	void add_edge_both(int from, int to, int cap)
  44. 	{
  45. 		if(cap>0)
  46. 		{
  47. 			const int rev_from	= SZ(G[from]);
  48. 			const int rev_to	= SZ(G[to]);
  49. 			G[from].push_back(edge(to,cap,rev_to));
  50. 			G[to].push_back(edge(from,cap,rev_from));
  51. 		}
  52. 	}
  53.  
  54. 	void add_edge(int from, int to, int cap)
  55. 	{
  56. 		if(cap>0)
  57. 		{
  58. 			const int rev_from	= SZ(G[from]);
  59. 			const int rev_to	= SZ(G[to]);
  60. 			G[from].push_back(edge(to,cap,rev_to));
  61. 			G[to].push_back(edge(from,0,rev_from));
  62. 		}
  63. 	}
  64.  
  65. 	// sからtへの最大流を求める
  66. 	int max_flow(int s, int t)
  67. 	{
  68. 		int flow = 0;
  69. 		for(;;)
  70. 		{
  71. 			bfs(s);
  72. 			if(level[t]<0) break;
  73. 			fill(iter.begin(),iter.end(),0);
  74. 			int f;
  75. 			while( (f=dfs(s,t,DINIC_INF))>0)
  76. 			{
  77. 				flow += f;
  78. 			}
  79. 		}
  80.  
  81. 		return flow;
  82. 	}
  83.  
  84. 	//  ノードsから辿れる範囲を求める（これ以上流せないところcap=0は、リンクがなくなる）
  85. 	// （流し終わったあとsourceからたどれる範囲が、最小カット時のs側。たどれない法がt側。その境界がカットするところ。）
  86. 	vector <bool> get_nodes_in_group(int s)
  87. 	{
  88. 		vector <bool> ret(maxv);
  89.  
  90. 		queue<int> que;
  91. 		que.push(s);
  92. 		while(!que.empty())
  93. 		{
  94. 			int v = que.front();
  95. 			que.pop();
  96. 			ret[v]=true;
  97.  
  98. 			for(int i=0;i<SZ(G[v]);i++)
  99. 			{
  100. 				edge &e = G[v][i];
  101. 				if(e.cap>0 && !ret[e.to])
  102. 				{
  103. 					que.push(e.to);
  104. 				}
  105. 			}
  106. 		}
  107. 		return ret;
  108. 	}
  109.  
  110. 	void disp()
  111. 	{
  112. 		for (int v = 0; v < maxv; v++)
  113. 		{
  114. 			printf("%d:",v);
  115. 			for(int i=0;i<SZ(G[v]);i++)
  116. 			{
  117. 				if(G[v][i].init_cap>0)
  118. 				{
  119. 					printf("->%d(%d),",G[v][i].to,G[v][i].init_cap);
  120. 				}
  121. 			}
  122. 			printf("\n");
  123. 		}
  124. 	}
  125.  
  126. private:
  127. 	// sからの最短距離をBFSで計算する
  128. 	void bfs(int s)
  129. 	{
  130. 		fill(level.begin(),level.end(),NG);
  131. 		queue<int> que;
  132. 		level[s]=0;
  133. 		que.push(s);
  134. 		while(!que.empty())
  135. 		{
  136. 			int v = que.front();
  137. 			que.pop();
  138. 			for(int i=0;i<SZ(G[v]);i++)
  139. 			{
  140. 				edge &e = G[v][i];
  141. 				if(e.cap>0 && level[e.to]<0)
  142. 				{
  143. 					level[e.to] = level[v] + 1;
  144. 					que.push(e.to);
  145. 				}
  146. 			}
  147. 		}
  148. 	}
  149.  
  150. 	// 増加パスをDFSで探す
  151. 	int dfs(int v, int t, int f)
  152. 	{
  153. 		if(v==t) return f;
  154. 		for (int &i=iter[v];i<SZ(G[v]);i++)
  155. 		{
  156. 			edge& e = G[v][i];
  157. 			if(e.cap>0 && level[v]<level[e.to])
  158. 			{
  159. 				int d = dfs(e.to, t, min(f, e.cap));
  160. 				if(d>0)
  161. 				{
  162. 					e.cap -= d;
  163. 					G[e.to][e.rev].cap += d;
  164. 					return d;
  165. 				}
  166. 			}
  167. 		}
  168. 		return 0;
  169. 	}
  170.  
  171. 	static const int DINIC_INF = INT_MAX; // 容量をllにしたいときは、ここも変える
  172.  
  173. 	struct edge 
  174. 	{
  175. 		edge(int input_to, int input_cap, int input_rev) : to(input_to), cap(input_cap), rev(input_rev), init_cap(input_cap) {}
  176. 		int to;		// 行先
  177. 		int cap;	// 容量
  178. 		int rev;	// 逆辺
  179. 		int init_cap; // 初期容量（デバッグ用）
  180. 	};
  181.  
  182. 	int	maxv;
  183. 	vector < vector <edge> > G;	// グラフの隣接リスト
  184. 	vector < int > level;		// sからの距離
  185. 	vector < int > iter;		// どこまで調べ終わったか
  186. };
  187.  
  188.  
  189. class SurroundingGame {
  190. public:
  191.  
  192.  
  193. 	int maxScore(vector <string> cost, vector <string> benefit) {
  194. // BEGIN CUT HERE
  195. 		// 1. 制約条件から読むこと
  196. 		// 2. 問題が理解できたら、Exampleで理解があってるか確認
  197. 		// 3. 解法が分からないときは、とにかく小さいケースの、「答え」を書き出す。プログラムも使って可
  198. 		// 4. それでも分からないときはグラフやx-y図を描く
  199. 		// MODの問題はlong longで。=0, =1, ="0001", ="0357"とか危険
  200. // END CUT HERE
  201. 		H = SZ(cost);
  202. 		W = SZ(cost[0]);
  203. 		const int S = H*W*2;
  204. 		const int T = S+1;
  205. 		const int V = T+1;
  206. 		Dinic*	dinic = new Dinic(V);
  207.  
  208. 		int totalDefaultProfit = 0;
  209. 		for (int y = 0; y < H; y++)
  210. 		{
  211. 			for (int x = 0; x < W; x++)
  212. 			{
  213.  
  214. 				//---------- 置く or 置かない ----------
  215. 				// 置く     profit = benefit-cost
  216. 				// 置かない profit = 0       
  217. 				{
  218. 					const int bc = getDecode(benefit[y][x])-getDecode(cost[y][x]);
  219. 					int capS;
  220. 					int capT;
  221.  
  222. 					if(bc>0)
  223. 					{
  224. 						// benefit-cost>0のとき
  225. 						// defaultProfit = benefit-cost
  226. 						// 置く     cap = defaultProfit - profit = 0
  227. 						// 置かない cap = defaultProfit - profit = benefit-cost
  228. 						capS = 0;	// 置く
  229. 						capT = bc;	// 置かない
  230. 						totalDefaultProfit += bc;
  231. 					}
  232. 					else
  233. 					{
  234. 						// benefit-cost<0のとき
  235. 						// defaultProfit = 0
  236. 						// 置く     cap = defaultProfit - profit = cost-benefit;
  237. 						// 置かない cap = defaultProfit - profit = 0;
  238. 						capS = -bc;	// 置く
  239. 						capT = 0;	// 置かない
  240. 					}
  241.  
  242. 					// 隣り合う条件を使うときに、二部グラフを利用。S側とT側を逆にする。
  243. 					if((x+y)&1)
  244. 					{
  245. 						swap(capS,capT);
  246. 					}
  247.  
  248. 					dinic->add_edge(S, oku(y,x), capS);
  249. 					dinic->add_edge(oku(y,x), T, capT);
  250. 				}
  251.  
  252. 				//---------- 囲まれない or 囲まれる ----------
  253. 				{
  254. 					const int b = getDecode(benefit[y][x]);
  255. 					// 囲まれない profit = 0
  256. 					// 囲まれる   profit = benefit
  257.  
  258. 					// この問題ではbenefitは常に0以上
  259. 					// defaultProfit = b
  260. 					// 囲まない cap = defaultProfit - profit = benefit;
  261. 					// 囲む     cap = defaultProfit - profit = 0;
  262. 					totalDefaultProfit += b;
  263. 					int capS = b;
  264. 					int capT = 0;
  265.  
  266. 					// 隣り合う条件を使うときに、二部グラフを利用。S側とT側を逆にする。
  267. 					if((x+y)&1)
  268. 					{
  269. 						swap(capS,capT);
  270. 					}
  271.  
  272. 					dinic->add_edge(S, kakomu(y,x), capS);
  273. 					dinic->add_edge(kakomu(y,x), T, capT);
  274. 				}
  275.  
  276. 				//----- 同じ場所で 置く && 囲まれる は同時に成立禁止 ----- 
  277. 				// 問題の条件より、置くか囲まれると、利益bもらえる。
  278. 				// このままだと、置いてかつ囲まれると、利益が2bもらえてしまう。
  279. 				// 置く && 囲む は同時に成立しても、グラフが切れないようにする。
  280. 				if((x+y)&1)
  281. 				{
  282. 					dinic->add_edge(oku(y,x), kakomu(y,x), BIG);
  283. 				}
  284. 				else
  285. 				{
  286. 					dinic->add_edge(kakomu(y,x), oku(y,x), BIG);
  287. 				}
  288.  
  289. 				//-----  囲まれる条件 ----- 
  290. 				// 囲まれるときは、隣の場所はすべて置く必要がある。
  291. 				// 言い換えると、囲まれたマスのまわりに、１個でも置かないマスがあったら、グラフが切れないようにする。
  292. 				const static int dy[] = {-1, 0, 1, 0}; // U,R,D,L
  293. 				const static int dx[] = { 0, 1, 0,-1};
  294. 				for(int d = 0; d < 4; d++)
  295. 				{
  296. 					const int ny = y+dy[d]; 
  297. 					const int nx = x+dx[d];
  298. 					if(INRANGE(ny,0,H-1)&&INRANGE(nx,0,W-1))
  299. 					{
  300. 						if((x+y)&1)
  301. 						{
  302. 							dinic->add_edge(oku(ny,nx), kakomu(y,x), BIG);
  303. 						}
  304. 						else
  305. 						{
  306. 							dinic->add_edge(kakomu(y,x), oku(ny,nx), BIG);
  307. 						}
  308. 					}
  309. 				}
  310. 			}
  311. 		}
  312.  
  313. 		const int result = totalDefaultProfit - dinic->max_flow(S,T);
  314.  
  315. 		delete dinic;
  316.  
  317. 		return result;
  318. 	}
  319.  
  320. private:
  321. 	int getDecode(const char c)
  322. 	{
  323. 		if(isdigit(c))
  324. 		{
  325. 			return c-'0';
  326. 		}
  327. 		else if (islower(c))
  328. 		{
  329. 			return c-'a'+10;
  330. 		}
  331. 		else if (isupper(c))
  332. 		{
  333. 			return c-'A'+36;
  334. 		}
  335.  
  336. 		return NG;
  337. 	}
  338.  
  339. 	int oku(int y, int x)
  340. 	{
  341. 		return y*W+x;
  342. 	}
  343. 	int kakomu(int y, int x)
  344. 	{
  345. 		return y*W+x+H*W;
  346. 	}
  347.  
  348. 	int H;
  349. 	int W;
  350.  
  351. private:
  352. 	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(); }
  353.  
  354. 	void verify_case(int Case, const int &Expected, const int &Received) { cerr << "Test Case #" << Case << "..."; if (Expected == Received) cerr << "PASSED" << endl; else { cerr << "FAILED" << endl; cerr << "\tExpected: \"" << Expected << '\"' << endl; cerr << "\tReceived: \"" << Received << '\"' << endl; } }
  355.  
  356. public:
  357. 	void run_test(int Case) { 
  358. 		int n = 0;
  359.  
  360. 		// test_case_0
  361. 		if ((Case == -1) || (Case == n)){
  362. 			string Arr0[] = {"21","12"};
  363. 			string Arr1[] = {"21","12"};
  364. 			int Arg2 = 4;
  365.  
  366. 			vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0])));
  367. 			vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0])));
  368. 			verify_case(n, Arg2, maxScore(Arg0, Arg1));
  369. 		}
  370. 		n++;
  371.  
  372. 		// test_case_1
  373. 		if ((Case == -1) || (Case == n)){
  374. 			string Arr0[] = {"ZZ","ZZ"};
  375. 			string Arr1[] = {"11","11"};
  376. 			int Arg2 = 0;
  377.  
  378. 			vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0])));
  379. 			vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0])));
  380. 			verify_case(n, Arg2, maxScore(Arg0, Arg1));
  381. 		}
  382. 		n++;
  383.  
  384. 		// test_case_2
  385. 		if ((Case == -1) || (Case == n)){
  386. 			string Arr0[] = {"XXX","XXX","XXX"};
  387. 			string Arr1[] = {"aaa","aZa","aaa"};
  388. 			int Arg2 = 2;
  389.  
  390. 			vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0])));
  391. 			vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0])));
  392. 			verify_case(n, Arg2, maxScore(Arg0, Arg1));
  393. 		}
  394. 		n++;
  395.  
  396. 		// test_case_3
  397. 		if ((Case == -1) || (Case == n)){
  398. 			string Arr0[] = {"asam","atik"};
  399. 			string Arr1[] = {"123A","45BC"};
  400. 			int Arg2 = 71;
  401.  
  402. 			vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0])));
  403. 			vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0])));
  404. 			verify_case(n, Arg2, maxScore(Arg0, Arg1));
  405. 		}
  406. 		n++;
  407.  
  408. 		// test_case_4
  409. 		if ((Case == -1) || (Case == n)){
  410. 			string Arr0[] = {"IIIIIIII",
  411.  "IIWWWWII",
  412.  "IIWIIIII",
  413.  "IIWIIIII",
  414.  "IIWWWWII",
  415.  "IIIIIWII",
  416.  "IIIIIWII",
  417.  "IIWWWWII",
  418.  "IIIIIIII"}
  419. ;
  420. 			string Arr1[] = {"IIIIIIII",
  421.  "II0000II",
  422.  "II0II0II",
  423.  "II0II0II",
  424.  "II0000II",
  425.  "II0II0II",
  426.  "II0II0II",
  427.  "II0000II",
  428.  "IIIIIIII"}
  429. ;
  430. 			int Arg2 = 606;
  431.  
  432. 			vector <string> Arg0(Arr0, Arr0 + (sizeof(Arr0) / sizeof(Arr0[0])));
  433. 			vector <string> Arg1(Arr1, Arr1 + (sizeof(Arr1) / sizeof(Arr1[0])));
  434. 			verify_case(n, Arg2, maxScore(Arg0, Arg1));
  435. 		}
  436. 		n++;
  437.  
  438. 	}
  439.  
  440. };
  441.  
  442. int main() {
  443. 	SurroundingGame* ___test = new SurroundingGame();
  444. 	___test->run_test(-1);
  445. 	delete ___test;
  446. }
  447.  
  448.  
Success #stdin #stdout #stderr 0s 3496KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
Test Case #0...PASSED
Test Case #1...PASSED
Test Case #2...PASSED
Test Case #3...PASSED
Test Case #4...PASSED
https://ideone.com/9kZXjO
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!