Submission #1519531

---

Source Code Expand

#include <bits/stdc++.h>
using namespace std;

#define maxn 202
#define FOR(i, l, r) for (int i=l; i<=r; ++i)
#define FORD(i, r, l) for (int i=r; i>=l; --i)
#define REP(i, r) for (int i=0; i<(int)r; ++i)
#define REPD(i, r) for (int i=(int)r-1; i>=0; --i)
#define fi first
#define se second
#define mk make_pair
#define nil NULL
#define y0 __y0
#define y1 __y1
#define x0 __x0
#define x1 __x1
#define next __next
#define sz size
#define Debug(X) {cerr << #X << " = " << X << '\n';}
#define PR(A, n) {cerr << #A << " = "; FOR(i, 1, n) cerr << A[i] << ' '; cerr << '\n';}
#define PR0(A, n) {cerr << #A << " = "; REP(i, n) cerr << A[i] << ' '; cerr << '\n';}
typedef long long ll;
typedef double db;
typedef pair<db, db> dd;
typedef pair<int, int> ii;
typedef vector<int> vi;
const int inf = 1e9;
template<class T> int getbit(T x, int pos) {return (x>>(pos-1)) & 1;}
template<class T> void turn_on(T &x, int pos) {x = x | ((T)1<<(pos-1));}
template<class T> void turn_off(T &x, int pos) {x = x & ~((T)1<<(pos-1));}
template<class T> T sqr(T a) {return a*a;}

int m, n, d[maxn], f[maxn][maxn], c[maxn][maxn], s, t;
char lake[maxn][maxn];
vector<int> a[maxn];
queue<int> qu;

bool findPath(int s, int t) {
    while (qu.sz()) qu.pop();
    qu.push(s);
    memset(d, 0, sizeof(d));
    while (qu.sz()) {
        int u = qu.front(); qu.pop();
        if (u==t) return true;
        REP(i, a[u].sz()) {
            int v = a[u][i];
            if (d[v]==0 && c[u][v]>f[u][v]) {
                d[v] = u;
                qu.push(v);
            }
        }
    }
    return false;
}

void incFlow() {
    int delta = inf;
    for (int v = t; v!=s; v = d[v]) delta = min(delta, c[d[v]][v] - f[d[v]][v]);
    for (int v = t; v!=s; v = d[v]) {
        f[d[v]][v] += delta;
        f[v][d[v]] -= delta;
    }
}

int main() {
    //freopen("lotus.inp", "r", stdin);
    //freopen(".out", "w", stdout);
    ios::sync_with_stdio(0); cin.tie(0);
    cin >> m >> n;
    FOR(i, 1, m) FOR(j, 1, n) cin >> lake[i][j];
    FOR(i, 1, m) FOR(j, 1, n) {
        if (lake[i][j]!='.') {
            a[i].push_back(m+j);
            a[m+j].push_back(i);
            if (lake[i][j]=='o') c[i][m+j] = c[m+j][i] = 1;
            else c[i][m+j] = c[m+j][i] = inf;
        }
        if (lake[i][j]=='S')
            s = i;
        if (lake[i][j]=='T')
            t = m+j;
    }
    while (findPath(s, t))
        incFlow();
    int res = 0;
    REP(i, a[s].sz()) {
        res += f[s][a[s][i]];
    }
    if (res>=inf) printf("-1");
    else printf("%d", res);
}

Submission Info

Judge Result