TopCoder SRM422 Div1Hard
問題
グリッド状の土地があり、金鉱、銀鉱、ワークスペースがある。それ以外のマスには芝生か岩である。
何人かの労働者を雇って、金銀の採掘をさせたい。各労働者には1つずつの金鉱、銀鉱、ワークスペースが与えられる。これらは複数人の労働者で共有してはいけない。
ワークスペースから、金鉱、銀鉱までの距離は、それぞれK以下でないといけない。移動の際に通れるマスは芝生のマスのみである。
雇える労働者の最大数を求めよ。
解答
ワークスペースと、金鉱、銀鉱の間で、つなげるかどうかの表をまず作成する。
これは、BFSによって各ワークスペースからの距離を求めることでできる。
その後、[起点]->[金鉱]->[ワークスペース1]->[ワークスペース2]->[銀鉱]->[終点]の有向グラフを作成する。
[起点]->[金鉱]間はすべての金鉱に対して結ぶ。
[金鉱]->[ワークスペース1]、[ワークスペース2]->[銀鉱]間はつなげられる間のみで結ぶ。
ワークスペース1とワークスペース2は、同じワークスペースを複数人で共有しないための措置である。ワークスペース1のi番目とワークスペース2のi番目を結ぶ。
その上で起点->終点で最大流を求めるとそれが答えである。
コード
#include <vector> #include <string> #include <algorithm> #include <queue> class dinic { /* for every edge (src, dest, cap, flow), it must have pair edge (dest, src, 0, -flow) */ struct edge { edge *next, *pair; int src, dest, cap, flow; }; int v, e; edge *pool, **con; int top; int* level; public: dinic(int _v, int _e) { v = _v; e = _e; pool = new edge[e]; con = new edge*[v]; for(int i=0;i<v;i++) con[i] = NULL; top = 0; } ~dinic() { delete [] pool; delete [] con; } edge* _add_edge(int src, int dest, int cap) { edge* ed = &(pool[top++]); ed->src = src; ed->dest = dest; ed->cap = cap; ed->flow = 0; ed->next = con[src]; con[src] = ed; return ed; } void add_pair(int src, int dest, int cap1, int cap2) { edge *e1 = _add_edge(src, dest, cap1); edge *e2 = _add_edge(dest, src, cap2); e1->pair = e2; e2->pair = e1; } int dfs(int s, int d, int cap) { if(s==d || cap==0) return cap; int w = 0; for(edge* ed = con[s]; ed != NULL; ed = ed->next) if(level[ed->dest] > level[s]){ int f = dfs(ed->dest, d, std::min(cap - w, ed->cap - ed->flow)); if(f > 0){ ed->flow += f; ed->pair->flow -= f; w += f; } } return w; } long long max_flow(int s, int d) { level = new int[v]; for(int i=0;i<e;i++) pool[i].flow = 0; long long ret = 0; for(bool update=true; update; ){ update = false; //derminate distance std::fill(level, level+v, -1); level[s] = 0; std::queue<int> q; q.push(s); int ps; while(!q.empty()){ ps = q.front(); q.pop(); for(edge* ed = con[ps]; ed != NULL; ed = ed->next){ if(ed->cap > ed->flow && level[ed->dest]==-1){ level[ed->dest] = level[ps] + 1; q.push(ed->dest); } } } for(;;){ int gain = dfs(s, d, 0x7FFFFFFF); if(gain==0) break; ret += gain; update = true; } } delete [] level; return ret; } }; using namespace std; int ax[4] = {-1, 0, 0, 1}; int ay[4] = {0, -1, 1, 0}; class WorkersOnPlane { int fld[32][32], H, W; int gold, silver, work; bool conWG[900][900], conWS[900][900]; void calc(int x, int y, int K) { for(int i=0;i<gold;i++) conWG[fld[x][y]][i] = false; for(int i=0;i<silver;i++) conWS[fld[x][y]][i] = false; int dist[32][32]; for(int i=0;i<H;i++) for(int j=0;j<W;j++) dist[i][j] = 100000; queue<pair<int, int> > q; dist[x][y] = 0; q.push(make_pair(x, y)); while(!q.empty()){ pair<int, int> p = q.front(); q.pop(); if(dist[p.first][p.second]>K) continue; if(fld[p.first][p.second]>=1000&&fld[p.first][p.second]<2000) conWG[fld[x][y]][fld[p.first][p.second]-1000] = true; if(fld[p.first][p.second]>=2000&&fld[p.first][p.second]<3000) conWS[fld[x][y]][fld[p.first][p.second]-2000] = true; if((p.first!=x||p.second!=y) && fld[p.first][p.second]!=-1) continue; for(int i=0;i<4;i++) if(dist[p.first+ax[i]][p.second+ay[i]] > dist[p.first][p.second]+1){ dist[p.first+ax[i]][p.second+ay[i]] = dist[p.first][p.second]+1; q.push(make_pair(p.first+ax[i], p.second+ay[i])); } } } public: int howMany(vector<string> field, int K) { H = field.size()+2; W = field[0].size()+2; for(int i=0;i<H;i++){ for(int j=0;j<W;j++) fld[i][j] = -2; } gold = silver = work = 0; for(int i=0;i<H-2;i++){ for(int j=0;j<W-2;j++){ if(field[i][j]=='.') fld[i+1][j+1] = -1; if(field[i][j]=='X') fld[i+1][j+1] = -2; if(field[i][j]=='W') fld[i+1][j+1] = work++; if(field[i][j]=='G') fld[i+1][j+1] = 1000 + gold++; if(field[i][j]=='S') fld[i+1][j+1] = 2000 + silver++; } } for(int i=0;i<H;i++) for(int j=0;j<W;j++) if(fld[i][j]>=0&&fld[i][j]<1000) calc(i, j, K); dinic dn(2000, 200000); for(int i=0;i<gold;i++) dn.add_pair(0, i+2, 1, 0); for(int i=0;i<silver;i++) dn.add_pair(2+gold+2*work+i, 1, 1, 0); for(int i=0;i<work;i++) dn.add_pair(2+gold+i, 2+gold+work+i, 1, 0); for(int i=0;i<work;i++){ for(int j=0;j<gold;j++) if(conWG[i][j]){ dn.add_pair(j+2, 2+gold+i, 1, 0); } for(int j=0;j<silver;j++) if(conWS[i][j]){ dn.add_pair(2+gold+work+i, 2+gold+2*work+j, 1, 0); } } return dn.max_flow(0, 1); } };