結果
問題 | No.421 しろくろチョコレート |
ユーザー |
![]() |
提出日時 | 2016-09-09 23:26:12 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 11 ms / 2,000 ms |
コード長 | 1,665 bytes |
コンパイル時間 | 655 ms |
コンパイル使用メモリ | 64,056 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-09-23 07:06:35 |
合計ジャッジ時間 | 2,134 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 65 |
ソースコード
#include <algorithm>#include <iostream>#include <vector>using namespace std;#define MAX_V 2500char choco[50][50];int V=MAX_V;vector<int> G[MAX_V];int match[MAX_V];bool used[MAX_V];void add_edge(int u,int v){G[u].push_back(v);G[v].push_back(u);}bool dfs(int v){used[v]=true;for(int i=0;i<G[v].size();i++){int u=G[v][i], w=match[u];if(w<0||(!used[w]&&dfs(w))){match[v]=u;match[u]=v;return true;}}return false;}int bipartite_matching(){int res=0;fill(match,match+MAX_V,-1);for(int v=0;v<V;v++){if(match[v]<0){fill(used,used+MAX_V,false);if(dfs(v)){res++;}}}return res;}int main(){int N,M;cin>>N>>M;for(int i=0;i<N;i++){for(int j=0;j<M;j++){cin>>choco[i][j];}}int white=0,black=0;for(int i=0;i<N;i++){for(int j=0;j<M;j++){if(choco[i][j]=='.') continue;if(choco[i][j]=='w'){white++;}else{black++;}int d[3]={0,1,0};for(int k=0;k<2;k++){int I=i+d[k],J=j+d[k+1];if(I>=0&&I<N&&J>=0&&J<M){if(choco[I][J]!='.'){add_edge(i*50+j,I*50+J);}}}}}int P=bipartite_matching();int score=100*P;white-=P;black-=P;score+=10*min(white,black);score+=max(white,black)-min(white,black);cout<<score<<endl;return 0;}