Submission #306342

---

Source Code Expand

#include<queue>
#include<cstdio>
#include<iostream>
#include<vector>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;

typedef long long LL;
typedef vector<int> VI;

#define REP(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define EACH(i,c) for(__typeof((c).begin()) i=(c).begin(),i##_end=(c).end();i!=i##_end;++i)
const int dx[] = {0,1,0,-1};
const int dy[] = {1,0,-1,0};

template<class T> inline void amin(T &a, const T &b) { if (a>b) a=b; }
template<class T> inline void amax(T &a, const T &b) { if (a<b) a=b; }
struct MinCostMaxFlow {
    typedef int Flow;
    typedef int Cost;
    static const Flow FLOW_INF = 1<<29;
    static const Cost COST_INF = 1<<29;
    struct Edge {
	int src, dst;
	Cost cst;
	Flow cap;
	int rev;
	int id;
	bool operator<(const Edge&y) const {
	    return cst > y.cst;
	}
    };
    typedef vector<vector<Edge> > Graph;
    Graph G;
    MinCostMaxFlow(int N) : G(N) {}
    // directed
    void add_edge(int u, int v, Cost x, Flow f, int id=-1) {
	G[u].push_back((Edge){ u, v, x, f, (int)G[v].size(), id });
	G[v].push_back((Edge){ v, u, -x, 0, (int)G[u].size()-1, -1 });
    }

    Flow flow;
    Cost cost;
    Flow solve(int s, int t, Flow limit = FLOW_INF) {
	flow = 0;
	cost = 0;
	vector<Cost>len, h(G.size(), 0);
	vector<int> prev, prev_num;
	while (limit > 0) {
	    priority_queue<Edge> Q;
	    Q.push((Edge){-2, s, 0, 0, 0});
	    len.assign(G.size(), COST_INF);
	    prev.assign(G.size(), -1); prev_num.assign(G.size(), -1);
	    len[s] = 0;
	    while (!Q.empty()) {
		Edge e = Q.top(); Q.pop();
		for (int i=0; i<(int)G[e.dst].size(); i++) {
		    const Edge &f = G[e.dst][i];
		    if (f.cap > 0 && len[f.dst] > len[f.src] + f.cst + h[f.src] - h[f.dst]) {
			len[f.dst] = len[f.src] + f.cst + h[f.src] - h[f.dst];
			Q.push((Edge){ f.src, f.dst, len[f.dst], 0, 0 });
			prev[f.dst] = f.src; prev_num[f.dst] = i;
		    }
		}
	    }
	    if (prev[t] == -1) return flow;
	    for (int i=0; i<(int)G.size(); i++) h[i] += len[i];
	    
	    Flow f = limit;
	    for (int v=t; v!=s; v=prev[v])
		f = min(f, G[prev[v]][prev_num[v]].cap);
	    for (int v=t; v!=s; v=prev[v]) {
		Edge &e = G[prev[v]][prev_num[v]];
		e.cap -= f;
		G[e.dst][e.rev].cap += f;
	    }
	    limit -= f;
	    flow += f;
	    cost += f * h[t];
	}
	return flow;
    }
};
const MinCostMaxFlow::Flow MinCostMaxFlow::FLOW_INF;
const MinCostMaxFlow::Cost MinCostMaxFlow::COST_INF;
int H, W;
char F[55][55];

int get(int y, int x, bool out) {
    return 2 * (y * W + x) + (int)(out);
}
pair<int, int>dec(int n) { // (y, x)
    return make_pair(n / 2 / W, n / 2 % W);
}

int L[55][55];
void solve() {
    int sx, sy;
    REP (i, H) REP (j, W) {
	if (F[i][j] == 'S') {
	    sx = j;
	    sy = i;
	}
    }
    memset(L, 0x3f, sizeof L);

    queue<int> qu;
    qu.push(sx); qu.push(sy);
    L[sy][sx] = 0;
    while (qu.size()) {
	int x = qu.front(); qu.pop();
	int y = qu.front(); qu.pop();
	REP (d, 4) {
	    int xx = x + dx[d];
	    int yy = y + dy[d];
	    if (0 <= xx && xx < W && 0 <= yy && yy < H &&
		    F[yy][xx] != '#' &&
		    L[yy][xx] > L[y][x] + 1) {
		L[yy][xx] = L[y][x] + 1;
		qu.push(xx);
		qu.push(yy);
	    }
	}
    }
}

int main() {
    scanf("%d%d", &H, &W);
    REP (i, H) scanf("%s", F[i]);
    solve();

    int cost = 0;
    REP (i, H) REP (j, W) {
	if (F[i][j] == 'A' || F[i][j] == 'B') cost += L[i][j];
    }

    int source = H*W*2, sink = source + 1;
    MinCostMaxFlow X(sink+1);

    REP (i, H) {
	REP (j, W) {
	    int v = get(i, j, 0);
	    int w = get(i, j, 1);
	    if (F[i][j] == 'A' || F[i][j] == 'B') {
		X.add_edge(v, w, 0, 1);
		X.add_edge(w, sink, 0, 1);
	    } else if (F[i][j] == 'S') {
		X.add_edge(v, w, 0, 2);
		X.add_edge(source, v, 0, 2);
	    } else if (F[i][j] != '#') {
		X.add_edge(v, w, 0, 1);
	    }

	    if (i) X.add_edge(w, get(i-1, j, 0), 1, 1, 1);
	    if (i<H-1) X.add_edge(w, get(i+1, j, 0), 1, 1, 1);
	    if (j) X.add_edge(w, get(i, j-1, 0), 1, 1, 1);
	    if (j<W-1) X.add_edge(w, get(i, j+1, 0), 1, 1);
	}
    }

    X.solve(source, sink);
    if (X.flow != 2 || X.cost != cost) {
	puts("NA");
	return 0;
    }

    REP (i, X.G.size()) {
	vector<MinCostMaxFlow::Edge> &v = X.G[i];
	REP (j, v.size()) {
	    if (v[j].src < source && v[j].dst < source && v[j].cap && v[j].dst < v[j].src) {
		int y = dec(v[j].src).first;
		int x = dec(v[j].src).second;
		int y2 = dec(v[j].dst).first;
		int x2 = dec(v[j].dst).second;
		if (x == x2 && y == y2) {
		    if (F[y][x] == '.') F[y][x] = 'a';
		}
	    }

	    if (i == sink) {
		int y = dec(v[j].dst).first;
		int x = dec(v[j].dst).second;
		if (F[y][x] == 'A') {
		    v[j].cap = 0;
		}
	    }
	}
    }

    X.solve(sink, source);
    REP (i, X.G.size()) {
	vector<MinCostMaxFlow::Edge> v = X.G[i];
	REP (j, v.size()) {
	    if (v[j].src < source && v[j].dst < source && v[j].cap && v[j].dst > v[j].src) {
		int y = dec(v[j].src).first;
		int x = dec(v[j].src).second;
		int y2 = dec(v[j].dst).first;
		int x2 = dec(v[j].dst).second;
		if (x == x2 && y == y2) {
		   if (F[y][x] == 'a') F[y][x] = 'b';
		}
	    }
	}
    }

    REP (i, H) puts(F[i]);

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:130:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
./Main.cpp:131:33: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]

Judge Result