Submission #1868981

---

Source Code Expand

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;

const int MaxN = 100;
const int MaxM = 100;

const int MaxNV = MaxN + MaxM + 2;
const int MaxNE = MaxN * MaxM + 2;

const int INF = 0x3f3f3f3f;

int n, m;
char s[MaxM + 2];

int vS, vT;

struct halfEdge
{
	int v, w;
	halfEdge *next;
};
halfEdge adj_pool[MaxNE * 2], *adj_tail = adj_pool;
halfEdge *adj[MaxNV + 1];

inline void addEdge(const int &u, const int &v, const int &wA, const int &wB = 0)
{
	adj_tail->v = v, adj_tail->w = wA, adj_tail->next = adj[u], adj[u] = adj_tail++;
	adj_tail->v = u, adj_tail->w = wB, adj_tail->next = adj[v], adj[v] = adj_tail++;
}

inline halfEdge *oppo(const halfEdge *e)
{
	return adj_pool + ((e - adj_pool) ^ 1);
}

int q_n, q[MaxNV + 1];

int lev[MaxNV + 1];
halfEdge *dfsCur[MaxNV + 1];

inline bool calc_dist()
{
	q_n = 0;
	for (int u = 1; u <= vT; ++u)
		lev[u] = -1, dfsCur[u] = adj[u];
	lev[vS] = 0;

	q[++q_n] = vS;
	for (int i = 1; i <= q_n; ++i)
	{
		int u = q[i];
		for (halfEdge *e = adj[u]; e; e = e->next)
			if (e->w && !~lev[e->v])
			{
				lev[e->v] = lev[u] + 1;
				if (e->v == vT)
					return true;
				q[++q_n] = e->v;
			}
	}

	return false;
}

int dfs(const int &u, const int &flow)
{
	if (u == vT || !flow)
		return flow;

	int res = 0;
	for (halfEdge *&e = dfsCur[u]; e; e = e->next)
		if (e->w && lev[e->v] > lev[u])
		{
			int delta = dfs(e->v, min(e->w, flow - res));
			if (delta > 0)
			{
				e->w -= delta, oppo(e)->w += delta;
				if ((res += delta) == flow)
					break;
			}
		}

	if (res < flow)
		lev[u] = -1;

	return res;
}

int main()
{
	cin >> n >> m;

	vS = n * m + 1, vT = vS + 1;
	for (int i = 1; i <= n; ++i)
	{
		scanf("%s", s + 1);

		for (int j = 1; j <= m; ++j)
		{
			if (s[j] == 'o')
				addEdge(i, j + n, 1, 1);
			else if (s[j] == 'S')
			{
				addEdge(vS, i + 0, INF);
				addEdge(vS, j + n, INF);
			}
			else if (s[j] == 'T')
			{
				addEdge(i + 0, vT, INF);
				addEdge(j + n, vT, INF);
			}
		}
	}

	int tot_flow = 0;
	while (tot_flow < INF && calc_dist())
		tot_flow += dfs(vS, INF);

	if (tot_flow >= INF)
		cout << -1 << endl;
	else
		cout << tot_flow << endl;

	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:100:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", s + 1);
                     ^

Judge Result