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 (123456789)
  36. #define BIGBIG (987654321987654321LL)
  37. #define SZ(a) ((int)((a).size()))
  38. #define SQ(a) ((a)*(a))
  39. typedef long long ll;
  40. typedef unsigned long long ull;
  41.  
  42. #define FOR(v,i) for(__typeof((v).begin())i=(v).begin();i!=(v).end();++i)
  43. // BEGIN CUT HERE
  44. #undef FOR
  45. #define FOR(v,i) for(auto i=(v).begin();i!=(v).end();++i)
  46. // END CUT HERE
  47.  
  48.  
  49. class Dinic
  50. {
  51. public:
  52.     Dinic(int input_maxv) : maxv(input_maxv)
  53.     {
  54.         G.resize(input_maxv);
  55.         level.resize(input_maxv);
  56.         iter.resize(input_maxv);
  57.     }
  58.  
  59.     void add_edge_both(int from, int to, int cap)
  60.     {
  61.         const int rev_from  = SZ(G[from]);
  62.         const int rev_to    = SZ(G[to]);
  63.         G[from].push_back(edge(to,cap,rev_to));
  64.         G[to].push_back(edge(from,cap,rev_from));
  65.     }
  66.  
  67.     void add_edge(int from, int to, int cap)
  68.     {
  69.         const int rev_from  = SZ(G[from]);
  70.         const int rev_to    = SZ(G[to]);
  71.         G[from].push_back(edge(to,cap,rev_to));
  72.         G[to].push_back(edge(from,0,rev_from));
  73.     }
  74.  
  75.     // sからtへの最大流を求める
  76.     int max_flow(int s, int t)
  77.     {
  78.         int flow = 0;
  79.         for(;;)
  80.         {
  81.             bfs(s);
  82.             if(level[t]<0) break;
  83.             fill(iter.begin(),iter.end(),0);
  84.             int f;
  85.             while( (f=dfs(s,t,DINIC_INF))>0)
  86.             {
  87.                 flow += f;
  88.             }
  89.         }
  90.  
  91.         return flow;
  92.     }
  93.  
  94.     //  ノードsから辿れる範囲を求める（これ以上流せないところcap=0は、リンクがなくなる）
  95.     // （流し終わったあとsourceからたどれる範囲が、最小カット時のs側。たどれない法がt側。その境界がカットするところ。）
  96.     vector <bool> get_nodes_in_group(int s)
  97.     {
  98.         vector <bool> ret(maxv);
  99.  
  100.         queue<int> que;
  101.         que.push(s);
  102.         while(!que.empty())
  103.         {
  104.             int v = que.front();
  105.             que.pop();
  106.             ret[v]=true;
  107.  
  108.             for(int i=0;i<SZ(G[v]);i++)
  109.             {
  110.                 edge &e = G[v][i];
  111.                 if(e.cap>0 && !ret[e.to])
  112.                 {
  113.                     que.push(e.to);
  114.                 }
  115.             }
  116.         }
  117.         return ret;
  118.     }
  119.  
  120.     void disp()
  121.     {
  122.         for (int v = 0; v < maxv; v++)
  123.         {
  124.             printf("%d:",v);
  125.             for(int i=0;i<SZ(G[v]);i++)
  126.             {
  127.                 if(G[v][i].init_cap>0)
  128.                 {
  129.                     printf("->%d(%d),",G[v][i].to,G[v][i].init_cap);
  130.                 }
  131.             }
  132.             printf("\n");
  133.         }
  134.     }
  135.  
  136. private:
  137.     // sからの最短距離をBFSで計算する
  138.     void bfs(int s)
  139.     {
  140.         fill(level.begin(),level.end(),NG);
  141.         queue<int> que;
  142.         level[s]=0;
  143.         que.push(s);
  144.         while(!que.empty())
  145.         {
  146.             int v = que.front();
  147.             que.pop();
  148.             for(int i=0;i<SZ(G[v]);i++)
  149.             {
  150.                 edge &e = G[v][i];
  151.                 if(e.cap>0 && level[e.to]<0)
  152.                 {
  153.                     level[e.to] = level[v] + 1;
  154.                     que.push(e.to);
  155.                 }
  156.             }
  157.         }
  158.     }
  159.  
  160.     // 増加パスをDFSで探す
  161.     int dfs(int v, int t, int f)
  162.     {
  163.         if(v==t) return f;
  164.         for (int &i=iter[v];i<SZ(G[v]);i++)
  165.         {
  166.             edge& e = G[v][i];
  167.             if(e.cap>0 && level[v]<level[e.to])
  168.             {
  169.                 int d = dfs(e.to, t, min(f, e.cap));
  170.                 if(d>0)
  171.                 {
  172.                     e.cap -= d;
  173.                     G[e.to][e.rev].cap += d;
  174.                     return d;
  175.                 }
  176.             }
  177.         }
  178.         return 0;
  179.     }
  180.  
  181.     static const int DINIC_INF = INT_MAX; // 容量をllにしたいときは、ここも変える
  182.  
  183.     struct edge 
  184.     {
  185.         edge(int input_to, int input_cap, int input_rev) : to(input_to), cap(input_cap), rev(input_rev), init_cap(input_cap) {}
  186.         int to;     // 行先
  187.         int cap;    // 容量
  188.         int rev;    // 逆辺
  189.         int init_cap; // 初期容量（デバッグ用）
  190.     };
  191.  
  192.     int maxv;
  193.     vector < vector <edge> > G; // グラフの隣接リスト
  194.     vector < int > level;     // sからの距離
  195.     vector < int > iter;      // どこまで調べ終わったか
  196.  
  197. };
  198.  
  199. int main()
  200. {
  201. 	int T;
  202. 	cin >> T;
  203.  
  204. 	for (int testcase = 0; testcase < T; testcase++)
  205. 	{
  206. 		int M,N;
  207. 		cin >> M >> N;
  208.  
  209. 		const int S = M*N;
  210. 		const int T = S+1;
  211. 		const int V = T+1;
  212. 		vector <string> vs;
  213. 		for (int y = 0; y < M; y++)
  214. 		{
  215. 			string s;
  216. 			cin >> s;
  217. 			vs.push_back(s);
  218. 		}
  219.  
  220.  
  221. 		const static int dy[] = {-1, 0, 1, 0}; // U,R,D,L
  222. 		const static int dx[] = { 0, 1, 0,-1};
  223.  
  224. 		Dinic* dinic = new Dinic(V);
  225.  
  226. 		int default_score = 0;
  227.  
  228.  
  229. 		for (int y = 0; y < M; y++)
  230. 		{
  231. 			for (int x = 0; x < N; x++)
  232. 			{
  233. 				const int now = y*N+x;
  234. 				if((x+y)%2==0)
  235. 				{
  236. 					if(vs[y][x]=='?')
  237. 					{
  238. 						default_score += 4;
  239. 						//						dinic->add_edge(S,now,0);
  240. 						dinic->add_edge(now,T,4);
  241.  
  242. 						for(int d = 0; d < 4; d++)
  243. 						{
  244. 							const int ny = y+dy[d]; 
  245. 							const int nx = x+dx[d];
  246. 							const int next = ny*N+nx;
  247. 							if(INRANGE(ny,0,M-1)&&INRANGE(nx,0,N-1))
  248. 							{
  249. 								if(vs[ny][nx]=='#' || vs[ny][nx]=='?')
  250. 								{
  251. 									dinic->add_edge(next,now,2);
  252. 								}
  253. 							}
  254. 						}
  255. 					}
  256. 					else if (vs[y][x]=='#')
  257. 					{
  258. 						default_score += 4;
  259. 						dinic->add_edge(now,T,BIG);
  260.  
  261. 						for(int d = 0; d < 4; d++)
  262. 						{
  263. 							const int ny = y+dy[d]; 
  264. 							const int nx = x+dx[d];
  265. 							if(INRANGE(ny,0,M-1)&&INRANGE(nx,0,N-1))
  266. 							{
  267. 								if(vs[ny][nx]=='#')
  268. 								{
  269. 									default_score -= 2;
  270. 								}
  271. 							}
  272. 						}
  273. 					}
  274. 				}
  275. 				else
  276. 				{
  277. 					if(vs[y][x]=='?')
  278. 					{
  279. 						default_score += 4;
  280.  
  281. 						dinic->add_edge(S,now,4);
  282. 						//						dinic->add_edge(now,T,0);
  283.  
  284. 						for(int d = 0; d < 4; d++)
  285. 						{
  286. 							const int ny = y+dy[d]; 
  287. 							const int nx = x+dx[d];
  288. 							const int next = ny*N+nx;
  289. 							if(INRANGE(ny,0,M-1)&&INRANGE(nx,0,N-1))
  290. 							{
  291. 								if(vs[ny][nx]=='#')
  292. 								{
  293. 									dinic->add_edge(now,next,2);
  294. 								}
  295. 							}
  296. 						}
  297. 					}
  298. 					else if (vs[y][x]=='#')
  299. 					{
  300. 						default_score += 4;
  301. 						dinic->add_edge(S,now,BIG);
  302. 					}
  303. 				}
  304. 			}
  305. 		}
  306.  
  307.  
  308. 		printf("Case #%d: %d\n",testcase+1,default_score - dinic->max_flow(S,T));
  309.  
  310. 		delete dinic;
  311. 	}
  312.  
  313.  
  314. 	return 0;
  315. }
  316.  
Success #stdin #stdout 0s 3492KB
comments (?)
stdin
copy 
2
3 3
.?.
.?.
.#.
5 8
.#...##.
.##..?..
.###.#.#
??#..?..
###?#...
stdout
copy 
Case #1: 8
Case #2: 42
https://ideone.com/wsv2RY
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!