結果
| 問題 | No.421 しろくろチョコレート |
| ユーザー |
|
| 提出日時 | 2017-01-14 20:58:50 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 5 ms / 2,000 ms |
| コード長 | 7,329 bytes |
| コンパイル時間 | 2,003 ms |
| コンパイル使用メモリ | 188,348 KB |
| 実行使用メモリ | 6,944 KB |
| 最終ジャッジ日時 | 2024-09-23 07:14:55 |
| 合計ジャッジ時間 | 3,593 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 65 |
ソースコード
#include<bits/stdc++.h>using namespace std;typedef unsigned int uint;typedef long long int ll;typedef unsigned long long int ull;#define debugv(v) printf("L%d %s => ",__LINE__,#v);for(auto e:v){cout<<e<<" ";}cout<<endl;#define debugm(m) printf("L%d %s is..\n",__LINE__,#m);for(auto v:m){for(auto e:v){cout<<e<<" ";}cout<<endl;}#define debuga(m,w) printf("L%d %s is => ",__LINE__,#m);for(int x=0;x<(w);x++){cout<<(m)[x]<<" ";}cout<<endl;#define debugaa(m,w,h) printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[x][y]<<" ";}cout<<endl;}#define debugaar(m,w,h) printf("L%d %s is..\n",__LINE__,#m);for(int y=0;y<(h);y++){for(int x=0;x<(w);x++){cout<<(m)[y][x]<<" ";}cout<<endl;}#define ALL(v) (v).begin(),(v).end()#define BIGINT 0x7FFFFFFF#define E107 1000000007llvoid printbit(int u){if(u==0)cout<<0;else{int s=0,k=0;for(;0<u;u>>=1,k++)s=(s<<1)|(u&1);for(;0<k--;s>>=1)cout<<(s&1);}}#define TIME chrono::system_clock::now()#define MILLISEC(t) (chrono::duration_cast<chrono::milliseconds>(t).count())namespace{std::chrono::system_clock::time_point t;void tic(){t=TIME;}void toc(){fprintf(stderr,"TIME : %lldms\n",MILLISEC(TIME-t));}}template<typename T1,typename T2>ostream& operator <<(ostream &o,const pair<T1,T2> p){o<<"("<<p.first<<":"<<p.second<<")";return o;}void safebreak(){static auto t = TIME;assert (MILLISEC(TIME-t) < 5000);}// todo : typedef int_c int // capacity// TODO:マーカーの実装？class Flow{public:size_t n;struct Arrow{int from,to;int w_max; // TODO: leftに改名int cap;Arrow(int from=0,int to=0,int w=1):from(from),to(to),w_max(w),cap(w){}bool operator<(const Arrow& a) const {return (from<a.from)|(to<a.to)|(w_max<a.w_max)|(cap<a.cap);}};vector<vector<int>> vertex_to;vector<vector<int>> vertex_from;vector<Arrow> arrow;Flow(int n,int m=5010):n(n),vertex_to(n),vertex_from(n){arrow.reserve(m);}void connect(int from, int to, int w_max){vertex_to[from].push_back(arrow.size()); // totovertex_from[to].push_back(arrow.size()); // fromfromarrow.emplace_back(from,to,w_max);}size_t degree(int v){return vertex_to[v].size() + vertex_from[v].size();}size_t degree_in(int v){return vertex_from[v].size();}size_t degree_out(int v){return vertex_to[v].size();}};// DAGint _dinic_path_dfs(Flow& flow, vector<int>& result, vector<bool>& flag, const vector<int>& dist, int u, int i_sink, int mini){// TODO: 経路再利用if (i_sink == u) return mini;if (flag[u]) return -1;flag[u] = true;int sumw = 0;bool term=true;for (int e : flow.vertex_to[u]){Flow::Arrow& a = flow.arrow[e];if (a.w_max > 0 && dist[u]>dist[a.to]){int w ;if (mini < 0)w = a.w_max;elsew = min(a.w_max, mini);w = _dinic_path_dfs(flow, result, flag, dist, a.to, i_sink, w);if (w==-1) continue;a.w_max -= w;result[a.to] += w;//printf("%d->%d (%d) : w=%d mini=%d \n",a.from,a.to,a.w_max+w,w,mini);sumw +=w;mini -=w;term = false;flag[u] = false;}}for (int e : flow.vertex_from[u]){Flow::Arrow& a = flow.arrow[e];if (a.cap>a.w_max && dist[u]>dist[a.from]){int w ;if (mini < 0)w = a.cap-a.w_max;elsew = min(a.cap-a.w_max, mini);w = _dinic_path_dfs(flow, result, flag, dist, a.from, i_sink, w);if (w==-1) continue;a.w_max += w;result[a.to] -= w;//printf("%d<-%d (%d) : w=%d mini=%d \n",a.from,a.to,a.w_max-w,w,mini);sumw +=w;mini -=w;term = false;flag[u] = false;}}return term ? -1 : sumw;}// flowは書き換えられる．void dinic(Flow &flow, vector<int>& result, int i_source, int i_sink){assert(i_source != i_sink);result.resize(flow.n);vector<int> dist(flow.n);queue<int> q;vector<bool> flag(flow.n); // TODO:for (int distbegin=0; ; distbegin+=flow.n){safebreak();q.emplace(i_sink); // bfsはsinkからsourceへの距離を計算．dist[i_sink] = distbegin+1;while (!q.empty()){int v = q.front();q.pop();for (int ie : flow.vertex_from[v]){const Flow::Arrow& e = flow.arrow[ie];if (0<e.w_max && dist[e.from] <= distbegin){dist[e.from] = dist[v]+1;q.emplace(e.from);}}for (int ie : flow.vertex_to[v]){const Flow::Arrow& e = flow.arrow[ie];if (e.w_max<e.cap && dist[e.to] <= distbegin){dist[e.to] = dist[v]+1;q.emplace(e.to);}}}//debugv(dist);fill(ALL(flag),false);if (dist[i_source] <= distbegin){break;}else{result[i_source] += _dinic_path_dfs(flow,result,flag,dist,i_source,i_sink,-1);}}}class BipartiteMatching{public:Flow flow;int n,m;int ss;BipartiteMatching(int n,int m):flow(2+n+m),n(n),m(m),ss(n+m){for (int i=0;i<n;i++)flow.connect(ss,i,1);for (int i=0;i<m;i++)flow.connect(n+i,ss+1,1);}void connect(int l,int r){flow.connect(l ,r+n ,1);}void solve_dinic(set<Flow::Arrow>& result){vector<int> r;dinic(flow,r,ss,ss+1);for (Flow::Arrow& a : flow.arrow){if (a.from==ss || a.to==ss+1) continue;if (a.w_max == 0){result.insert(a);}}}};int width,height;int m,n;string cho[55];int main(){int i,j,k;int x,y,a,b;cin >> height >> width;n = height*width;BipartiteMatching bm(n,n);for (y=0;y<height;y++){cin >> cho[y];}int white,black;white=black=0;for (y=0;y<height;y++){for (x=0;x<width;x++){if (cho[y][x]=='.') continue;if (cho[y][x]=='w')white++;elseblack++;if ((y^x)&1) continue;if (0 < x && cho[y][x-1]!='.')bm.connect(x+y*width,x-1+y*width);if (0 < y && cho[y-1][x]!='.')bm.connect(x+y*width,x+(y-1)*width);if (width-1 > x && cho[y][x+1]!='.')bm.connect(x+y*width,x+1+y*width);if (height-1 > y && cho[y+1][x]!='.')bm.connect(x+y*width,x+(y+1)*width);}}set<Flow::Arrow> pairs;bm.solve_dinic(pairs);int np = pairs.size();white -= np;black -= np;cout << ( (np*100) + (min(white,black)*10) + abs(white-black) ) << endl;return 0;}