Submission #306309

---

Source Code Expand

#include <bits/stdc++.h>

#define rep(i,n) for(int i=0;i<(int)(n);i++)
#define each(it,n) for(__typeof((n).begin()) it=(n).begin();it!=(n).end();++it)

using namespace std;

typedef long long ll;

struct edge{int to, cap, cost, rev, ocap;};

class MinCostFlow {
public:
    typedef int Int;
    typedef pair<Int, Int> P;
    const Int INF = 1LL << 29;
    
    Int N;
    vector<vector<edge> > G;
    vector<Int> h, dist, prevv, preve;
    
    MinCostFlow(Int N) {
        this->N = N;
        G = vector<vector<edge> >(N);
        h = vector<Int>(N);
        dist = vector<Int>(N);
        prevv = vector<Int>(N);
        preve = vector<Int>(N);
    }
    
    void add_edge(Int from, Int to, Int cap, Int cost) {
        edge e, re;
        e.to = to, e.cap = cap, e.cost = cost, e.rev = G[to].size(), e.ocap = cap;
        G[from].push_back(e);
        re.to = from, re.cap = 0, re.cost = -cost, re.rev = G[from].size() - 1, re.ocap = 0;
        G[to].push_back(re);
    }
    
    Int run(Int s, Int t, Int f) {
        Int res = 0;
        fill(h.begin(), h.end(), 0);
        //fill(prevv.begin(), prevv.end(), 0);
        //fill(preve.begin(), preve.end(), 0);
        while (f > 0) {
            priority_queue<P, vector<P>, greater<P> > que;
            fill(dist.begin(), dist.end(), INF);
            dist[s] = 0;
            que.push(P(0, s));
            while (!que.empty()) {
                P p = que.top(); que.pop();
                Int v = p.second;
                if (dist[v] < p.first) continue;
                for (Int i = 0; i < (Int)G[v].size(); i++) {
                    edge &e = G[v][i];
                    if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
                        dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
                        prevv[e.to] = v;
                        preve[e.to] = i;
                        que.push(P(dist[e.to], e.to));
                    }
                }
            }
            if (dist[t] == INF) {
                return -INF;
            }
            for (Int v = 0; v < N; v++) h[v] += dist[v];
            
            Int d = f;
            for (Int v = t; v != s; v = prevv[v]) {
                d = min(d, G[prevv[v]][preve[v]].cap);
            }
            f -= d;
            res += d * h[t];
            for (Int v = t; v != s; v = prevv[v]) {
                edge &e = G[prevv[v]][preve[v]];
                e.cap -= d;
                G[v][e.rev].cap += d;
            }
        }
        return res;
    }
};

int di[4] = {0, 1, 0, -1}, dj[4] = {1, 0, -1, 0};

int h, w;
int id(int i, int j, bool source) {
    return source ? i * w + j : h * w + i * w + j;
}

int main() {
    cin >> h >> w;
    
    vector<string> field(h);
    rep(i, h) {
        cin >> field[i];
    }

    MinCostFlow flow(h * w * 2 + 1);
    int sink = h * w * 2;

    int si, sj, ai, aj, bi, bj;
    int sid, aid, bid;

    rep(i, h) {
        rep(j, w) {
            if (field[i][j] == '#') continue;
            if (field[i][j] == 'S') {
                si = i, sj = j;
                sid = id(i, j, false);
            }
            if (field[i][j] == 'A') {
                ai = i, aj = j;
                aid = id(i, j, false);
                flow.add_edge(aid, sink, 1, 0);
            }
            if (field[i][j] == 'B') {
                bi = i, bj = j;
                bid = id(i, j, false);
                flow.add_edge(bid, sink, 1, 0);
            }
            flow.add_edge(id(i, j, true), id(i, j, false), 1, 1);

            rep(k, 4) {
                int ti = i + di[k], tj = j + dj[k];
                if (ti < 0 || h <= ti || tj < 0 || w <= tj) continue;
                if (field[ti][tj] == '#') continue;
                flow.add_edge(id(i, j, false), id(ti, tj, true), 1, 0);
            }
        }
    }
    int sa, sb;
    {
        MinCostFlow tmp = flow;
        sa = tmp.run(sid, aid, 1);
    }
    {
        MinCostFlow tmp = flow;
        sb = tmp.run(sid, bid, 1);
    }

    int ans = flow.run(sid, sink, 2);
    cerr << ans << " " << sa << " " << sb << endl;

    if (ans != sa + sb) {
        cout << "NA" << endl;
        return 0;
    }

    rep(k, 2) {
        int id = sid;
        vector<int> pathi, pathj;
        while (id != aid && id != bid) {
            if (id < h * w) {
                pathi.push_back(id / w);
                pathj.push_back(id % w);
            }
            rep(i, flow.G[id].size()) {
                edge &e = flow.G[id][i];
                if (e.cap == 0 && e.cap != e.ocap) {
                    e.cap = e.ocap;
                    id = e.to;
                    break;
                }
            }
        }

        if (id == aid) {
            rep(i, pathi.size() - 1) {
                field[pathi[i]][pathj[i]] = 'a';
            }
        } else {
            rep(i, pathi.size() - 1) {
                field[pathi[i]][pathj[i]] = 'b';
            }
        }
    }

    rep(i, h) {
        cout << field[i] << endl;
    }

    return 0;
}

Submission Info

Judge Result