2008-10-22
SRM422 Div1 Hard: WorkersOnPlane
練習のために前回（SRM 422）のDIV1 1000点問題「WorkersOnPlane」を開いてみた。1000点問題のコーディングは初挑戦。
- Worker１人がそれぞれ Gold x 1, Silver x 1 を担当。
- W(Workplace)から距離K以内のG(Gold),S(Silver)のみ担当可能。マップには途中障害物あり。
解けるかも・・・
- マップを走査し、W,G,Sを探してそれぞれにidを振る
- 各Wから到達可能なG,Sをすべて抽出
- WからK以内で到達可能な領域をFlood Fill的にBFS(+priority queue)探索
- どこからも到達不能なG,Sはネットワークに入れない
- W-G-S の組をできるだけ多く作る
やっとMaximum Flowを使える問題が来たよ
- start < G x W = W x S > end
- G,W,Sはそれぞれ複数ノード。
- x は複数の辺がクロスしているイメージ。
- = は１対１で平行に繋がっている
- <, > は１対多で繋がっている
- 各辺のキャパシティは1
- とりあえずナイーブに辿れるルートをカウント（一度通った道は通れない）
- W = W を入れることで、同じWを使うルートがいくつも出来てしまうのを防ぐことができる。
- residual networkを作って、カウントを増やしていく（問題文のテストケースでは、residual networkが必要な問題はない）
submitしてみたが、System Testの６番（マップ大きめ）で落ちる。
- マップ内のSの個数がW,Gと違った
- 一度通った道は通れない、ようにしたつもりだったがチェックしていない箇所があったorz
で無事「120」が出るようになった。
これを時間内に解ければ点が貰えるんですね。
時間内に・・・＞＜
書いたコードを晒してみる：
#include <string>
#include <vector>
#include <map>
#include <set>
#include <queue>
using namespace std;
#define tr(c,i) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define found(s,e) ((s).find(e)!=(s).end())
class WorkersOnPlane {
public:
int howMany(vector<string> field, int K) {
int rows = field.size();
int cols = field[0].size();
vector<pair<int,int> > W;
map<pair<int,int>, int> G, S;
int gcount = 0, scount = 0;
for (int y=0; y<rows; y++) {
for (int x=0; x<cols; x++) {
int c = field[y][x];
switch (c) {
case 'W': W.push_back( make_pair(y,x) ); break;
case 'G': G[ make_pair(y,x) ] = gcount++; break;
case 'S': S[ make_pair(y,x) ] = scount++; break;
default: break;
}
}
}
int wcount = W.size();
int nodes = 1 + gcount + wcount * 2 + scount + 1;
const int START = 0,
GSTART = 1,
WgSTART = GSTART + gcount,
WsSTART = WgSTART + wcount,
SSTART = WsSTART + wcount,
END = nodes - 1; // SSTART + scount
vector<map<int,pair<int,int> > > arc(nodes);
for (int g=0; g<gcount; g++) arc[START][GSTART+g] = make_pair(0,1);
for (int w=0; w<wcount; w++) arc[WgSTART+w][WsSTART+w] = make_pair(0,1);
for (int s=0; s<scount; s++) arc[SSTART+s][END] = make_pair(0,1);
for (int w=0; w<wcount; w++) {
int y = W[w].first, x = W[w].second;
vector<vector<int> > d(rows); // distance
for (int y=0; y<rows; y++) {
d[y].resize(cols);
for (int x=0; x<cols; x++) {
d[y][x] = INT_MAX;
}
}
priority_queue<pair<int,pair<int,int> > > pq;
pq.push(make_pair(0,make_pair(y,x)));
do {
int y = pq.top().second.first;
int x = pq.top().second.second;
int d_ = -pq.top().first;
pq.pop();
if (d_ >= d[y][x]) continue;
switch (field[y][x]) {
case 'W':
if (d_ != 0) break;
// fall through
case '.':
d[y][x] = d_; //min(d_, d[y][x]);
if (d_ < K) {
if (x >= 1)
pq.push(make_pair(-d_-1,make_pair(y,x-1)));
if (x+1 < cols)
pq.push(make_pair(-d_-1,make_pair(y,x+1)));
if (y >= 1)
pq.push(make_pair(-d_-1,make_pair(y-1,x)));
if (y+1 < rows)
pq.push(make_pair(-d_-1,make_pair(y+1,x)));
}
break;
case 'G':
{
d[y][x] = d_;
int g = G[ make_pair(y,x) ];
arc[GSTART+g][WgSTART+w] = make_pair(0,1);
}
break;
case 'S':
{
d[y][x] = d_;
int s = S[ make_pair(y,x) ];
arc[WsSTART+w][SSTART+s] = make_pair(0,1);
}
break;
case 'X':
break;
}
} while (!pq.empty());
}
// remove unreachable Gs/Ss
for (int g=0; g<gcount; g++) {
if (arc[GSTART+g].size() == 0) {
arc[START].erase(GSTART+g);
}
}
vector<bool> ss(scount,false);
for (int w=0; w<wcount; w++) {
tr(arc[WsSTART+w],st) { ss[st->first - SSTART] = true; }
}
for (int s=0; s<scount; s++) {
if (!ss[s]) {
arc[SSTART+s].erase(END);
}
}
// initial
vector<vector<int> > ways;
for (int g_=0; g_<gcount; g_++) {
int g = GSTART+g_;
bool viable = false;
tr(arc[g],at) {
if (at->second.first == 1) continue;
int w = at->first; // key
if (arc[w][w+wcount].first == 1) continue;
tr(arc[w+wcount],bt) {
// bt = arc[ws][s]
if (bt->second.first == 1) continue;
int s = bt->first; // key
if (arc[s][END].first == 1) continue;
int way_[6] = { START, g, w, w+wcount, s, END };
vector<int> way(way_, way_+6);
ways.push_back(way);
arc[START][g].first = 1; // START - G
arc[g][w].first = 1; // G - Wg
arc[w][w+wcount].first = 1; // Wg - Ws
arc[w+wcount][s].first = 1; // Ws - S
arc[s][END].first = 1; // S - END
viable = true;
break;
}
if (viable) break;
}
}
// residual networks
vector<map<int,int> > resid(nodes);
for (int j=0; j<nodes; j++) {
tr(arc[j],at) {
int k = at->first;
resid[j][k] = arc[j][k].second - arc[j][k].first;
resid[k][j] = arc[j][k].first;
}
}
if (ways.size() == arc[START].size()) return ways.size();
// find another way
for (int i=0; ;i++) {
bool another_way = false;
vector<int> prev(nodes,INT_MAX);
queue<pair<int,int> > q;
q.push(make_pair(START,-1));
while (!q.empty()) {
pair<int,int> p = q.front();
int node = p.first, prev_node = p.second;
q.pop();
prev[node] = prev_node;
if (node == END) {
another_way = true;
break;
}
tr(resid[node],rt) {
if (rt->second == 0) continue;
if (prev[rt->first] < INT_MAX) continue;
q.push(make_pair(rt->first, node));
}
}
// no more ways
if (!another_way) return ways.size() + i;
for (int node=END; node!=START; node=prev[node]) {
int prev_node = prev[node];
resid[prev_node][node]--;
resid[node][prev_node]++;
}
}
return 0;
}
};
- Ford-Fulkerson法
- この問題では ways[] に見つかった経路を保持する意味合いは特にない。ちゃんと見つかっているかどうかデバッグ時に知るのに役に立つだけ。
追記
nitoyonさんの裏ログに解説がw
コメント
トラックバック - https://topcoder-g-hatena-ne-jp.jag-icpc.org/n4_t/20081022