Submission #1298650

---

Source Code Expand

#include <stdio.h>
#include <vector>
#include <limits.h>
#include <queue>
#include <string.h>
#include <algorithm>
#include <functional>
using namespace std;

//total # of nodes
const int MAXN = 20005;

struct Maxflow {
	struct E {
		int x, inv, cap, flow;
		E(int t, int c, int z) : x(t), inv(z), cap(c), flow(0) {}
		int rest() const { return cap - flow; }
	};
	int V, d[MAXN], e_try[MAXN];
	vector <E> g[MAXN];
	Maxflow(int V) : V(V) {}
	void addedge(int a, int b, int a2b, int b2a = 0) {
		int as = g[a].size(), bs = g[b].size();
		g[a].push_back({ b, a2b, bs });
		g[b].push_back({ a, b2a, as });
	}
	bool bfs(int S, int T) {
		memset(d, -1, sizeof(d));
		queue <int> q; q.push(S);
		d[S] = 0;
		while (!q.empty()) {
			int x = q.front(); q.pop();
			for (auto &e : g[x]) {
				if (d[e.x] == -1 && e.rest() > 0) {
					d[e.x] = d[x] + 1;
					q.push(e.x);
				}
			}
		}
		return d[T] != -1;
	}
	int dfs(int x, int T, int flow) {
		if (x == T) return flow;
		for (int& i = e_try[x]; i < g[x].size(); i++) {
			E &e = g[x][i];
			if (e.rest() > 0 && d[e.x] == d[x] + 1) {
				int t = dfs(e.x, T, min(flow, e.rest()));
				if (t > 0) {
					E &re = g[e.x][e.inv];
					e.flow += t;
					re.flow = -e.flow;
					return t;
				}
			}
		}
		return 0;
	}
	int go(int S, int T) {
		int res = 0, t = 0;
		while (bfs(S, T)) {
			memset(e_try, 0, sizeof(e_try));
			do {
				t = dfs(S, T, numeric_limits<int>::max());
				res += t;
			} while (t);
		}
		return res;
	}
};
int N, M, sx, sy, tx, ty, n, c[105][105];
char S[105][105];
int main() {
	scanf("%d%d", &N, &M);
	for (int i = 1; i <= N; i++) {
		scanf("%s", S[i] + 1);
		for (int j = 1; j <= M; j++) {
			if (S[i][j] == 'S') sx = i, sy = j, c[i][j] = ++n;
			if (S[i][j] == 'T') tx = i, ty = j, c[i][j] = ++n;
			if (S[i][j] == 'o') c[i][j] = ++n;
		}
	}
	Maxflow f(2 * n + 1);
	if (sx == tx || sy == ty) puts("-1");
	else {
		for (int i = 1; i <= n; i++) {
			if (i == c[sx][sy] || i == c[tx][ty]) continue;
			f.addedge(2 * i - 1, 2 * i, 1, 0);
		}
		f.addedge(2 * c[sx][sy] - 1, 2 * c[sx][sy], n, 0);
		f.addedge(2 * c[tx][ty] - 1, 2 * c[tx][ty], n, 0);
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= M; j++) {
				if (c[i][j]) {
					int x = c[i][j];
					for (int k = 1; k <= M; k++) {
						if (j == k) continue;
						if (c[i][k]) {
							int y = c[i][k];
							f.addedge(2 * x, 2 * y - 1, 1, 0);
						}
					}
					for (int k = 1; k <= N; k++) {
						if (i == k) continue;
						if (c[k][j]) {
							int y = c[k][j];
							f.addedge(2 * x, 2 * y - 1, 1, 0);
						}
					}
				}
			}
		}
		int res = f.go(2 * c[sx][sy] - 1, 2 * c[tx][ty]);
		printf("%d", res);
	}
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:73:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
                       ^
./Main.cpp:75:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", S[i] + 1);
                        ^

Judge Result