結果

問題 No.421 しろくろチョコレート
ユーザー chocoruskchocorusk
提出日時 2018-09-20 06:32:26
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 4 ms / 2,000 ms
コード長 2,088 bytes
コンパイル時間 824 ms
コンパイル使用メモリ 87,908 KB
実行使用メモリ 6,944 KB
最終ジャッジ日時 2024-09-23 07:17:53
合計ジャッジ時間 2,607 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,812 KB
testcase_01 AC 3 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,940 KB
testcase_04 AC 2 ms
6,944 KB
testcase_05 AC 2 ms
6,940 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 2 ms
6,940 KB
testcase_10 AC 2 ms
6,944 KB
testcase_11 AC 2 ms
6,944 KB
testcase_12 AC 2 ms
6,940 KB
testcase_13 AC 2 ms
6,944 KB
testcase_14 AC 2 ms
6,940 KB
testcase_15 AC 1 ms
6,940 KB
testcase_16 AC 4 ms
6,944 KB
testcase_17 AC 4 ms
6,944 KB
testcase_18 AC 4 ms
6,944 KB
testcase_19 AC 2 ms
6,940 KB
testcase_20 AC 3 ms
6,940 KB
testcase_21 AC 3 ms
6,944 KB
testcase_22 AC 3 ms
6,944 KB
testcase_23 AC 2 ms
6,944 KB
testcase_24 AC 2 ms
6,944 KB
testcase_25 AC 2 ms
6,944 KB
testcase_26 AC 1 ms
6,940 KB
testcase_27 AC 2 ms
6,940 KB
testcase_28 AC 2 ms
6,940 KB
testcase_29 AC 2 ms
6,944 KB
testcase_30 AC 3 ms
6,940 KB
testcase_31 AC 4 ms
6,940 KB
testcase_32 AC 2 ms
6,944 KB
testcase_33 AC 2 ms
6,940 KB
testcase_34 AC 2 ms
6,940 KB
testcase_35 AC 2 ms
6,940 KB
testcase_36 AC 2 ms
6,940 KB
testcase_37 AC 3 ms
6,944 KB
testcase_38 AC 4 ms
6,944 KB
testcase_39 AC 2 ms
6,944 KB
testcase_40 AC 2 ms
6,944 KB
testcase_41 AC 2 ms
6,944 KB
testcase_42 AC 2 ms
6,940 KB
testcase_43 AC 2 ms
6,940 KB
testcase_44 AC 2 ms
6,940 KB
testcase_45 AC 2 ms
6,944 KB
testcase_46 AC 2 ms
6,940 KB
testcase_47 AC 3 ms
6,940 KB
testcase_48 AC 2 ms
6,940 KB
testcase_49 AC 2 ms
6,944 KB
testcase_50 AC 2 ms
6,940 KB
testcase_51 AC 3 ms
6,944 KB
testcase_52 AC 2 ms
6,940 KB
testcase_53 AC 2 ms
6,944 KB
testcase_54 AC 2 ms
6,940 KB
testcase_55 AC 2 ms
6,944 KB
testcase_56 AC 2 ms
6,944 KB
testcase_57 AC 2 ms
6,940 KB
testcase_58 AC 3 ms
6,944 KB
testcase_59 AC 2 ms
6,944 KB
testcase_60 AC 4 ms
6,944 KB
testcase_61 AC 4 ms
6,940 KB
testcase_62 AC 2 ms
6,944 KB
testcase_63 AC 1 ms
6,944 KB
testcase_64 AC 2 ms
6,940 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;
const ll INF=1e16;
struct edge {int to; long long int cap; int rev;} ;
 
vector<edge> G[2502];
int level[2502];
int iter[2502];
 
void add_edge(int from, int to, long long int cap){
	edge e;
	e.to=to, e.cap=cap, e.rev=G[to].size();
	G[from].push_back(e);
	e.to=from, e.cap=0, e.rev=G[from].size()-1;
	G[to].push_back(e);
}
 
void bfs(int s){
	memset(level, -1, sizeof(level));
	queue<int> que;
	level[s]=0;
	que.push(s);
	while(!que.empty()){
		int v=que.front();
		que.pop();
		for(int i=0; i<G[v].size(); i++){
			edge e=G[v][i];
			if(e.cap>0 && level[e.to]<0){
				level[e.to]=level[v]+1;
				que.push(e.to);
			}
		}
	}
}
 
long long int dfs(int v, int t, long long int f){
	if(v==t) return f;
	for(int &i=iter[v]; i<G[v].size(); i++){
		edge &e=G[v][i];
		if(e.cap>0 && level[v]<level[e.to]){
			long long int d=dfs(e.to, t, min(f, e.cap));
			if(d>0){
				e.cap-=d;
				G[e.to][e.rev].cap+=d;
				return d;
			}
		}
	}
	return 0;
}
 
long long int max_flow(int s, int t){
	long long int flow=0;
	while(1){
		bfs(s);
		if(level[t]<0) return flow;
		memset(iter, 0, sizeof(iter));
		long long int f;
		while((f=dfs(s, t, INF))>0){
			flow+=f;
		}
	}
}

int main()
{
	int n, m;
	cin>>n>>m;
	string s[50];
	int cw=0, cb=0;
	for(int i=0; i<n; i++){
		cin>>s[i];
	}
	int dx[4]={1, -1, 0, 0}, dy[4]={0, 0, 1, -1};
	int V=n*m+2;
	for(int i=0; i<n; i++){
		for(int j=0; j<m; j++){
			if(s[i][j]=='.') continue;
			if((i+j)%2){
				cb++;
				add_edge(i*m+j, V-1, 1ll);
				for(int k=0; k<4; k++){
					if(0<=i+dx[k] && i+dx[k]<n && 0<=j+dy[k] && j+dy[k]<m && s[i+dx[k]][j+dy[k]]!='.'){
						add_edge((i+dx[k])*m+(j+dy[k]), i*m+j, 1ll);
					}
				}
			}else{
				cw++;
				add_edge(V-2, i*m+j, 1ll);
			}
		}
	}
	int mx=max_flow(V-2, V-1);
	cout<<abs(cw-cb)+10*(min(cw, cb)-mx)+100*mx<<endl;
	return 0;
}
0