Language: C++

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <fstream>
#include <iostream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <bitset>
#include <array>
#include <vector>
#include <queue>
#include <set>
#include <cmath> // 変数名にy1が使えなくなるかも…。
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <limits>
#include <string>

typedef __int128_t int128_t;
std::istream &operator>>(std::istream& input, int128_t& value) { // int128_tの入力。入力が64bitに収まる前提。
    long long tmp; input >> tmp; value = tmp;
    return input;
}
std::ostream &operator<<(std::ostream& output, const int128_t value) { // int128_tの出力。出力が64bitに収まる前提。
    output << (long long)value;
    return output;
}

class Directed_Graph {
    public:
    struct Edge { 
        int to; int64_t cost;
    };
    typedef std::vector<std::vector<Edge>> adj_list;
    adj_list G;
    int node_num;
    Directed_Graph() {}
    Directed_Graph(const int node_num_in) {
        node_num = node_num_in;
        G.resize(node_num);
    }
    void add_edge(const int from, const int to, const long long cost) {
        Edge edge; edge.to = to; edge.cost = cost;
        G[from].push_back(edge);
    }
    void add_edge_both(const int node1, const int node2, const long long cost) {
        add_edge(node1, node2, cost);
        add_edge(node2, node1, cost);
    }

    // 点sからの最短距離の配列を返す。
    // 戻りの値としてint128_tを用い、初期値としてint64_tの最大値を用いるのは、dist[v] + edge.costの計算でのオーバーフローを防ぐため。
    // 正しい最短距離がint64_tの最大値を超えるような事態は想定していないので、最終的にdist[v] == std::numeric_limits<int64_t>::max()だった場合、vには到達できないことを意味する。
    std::vector<int128_t> Dijkstra(int s) {
        std::vector<int128_t> dist;
        dist.resize(node_num, std::numeric_limits<int64_t>::max());

        typedef std::pair<int128_t, int> Pair;
        std::priority_queue <Pair, std::vector<Pair>, std::greater<Pair>> que;
        dist[s] = 0;
        que.push(Pair(0, s));

        while (!que.empty()) {
            Pair pair = que.top(); que.pop();
            int v = pair.second;
            if (dist[v] < pair.first) { continue; }
            for (Edge edge : G[v]) {
                if (dist[v] + edge.cost < dist[edge.to]) {
                    dist[edge.to] = dist[v] + edge.cost;
                    que.push(Pair(dist[edge.to], edge.to));
                }
            }
        }
        return dist;
    }

    std::vector<std::vector<long long>> Warshall_Floyd(const long long dist_inf) {
        std::vector<std::vector<long long>> dist; dist.resize(node_num);
        for (int i = 0; i < dist.size(); i++) {
            dist[i].resize(node_num);
            for (int j = 0; j < dist[i].size(); j++) {
                dist[i][j] = dist_inf;
            }
            dist[i][i] = 0;
            for (auto e : G[i]) {
                dist[i][e.to] = std::min(dist[i][e.to], e.cost);
            }
        }
        for (int k = 0; k < node_num; k++) {
            for (int i = 0; i < node_num; i++) {
                for (int j = 0; j < node_num; j++) {
                    dist[i][j] = std::min(dist[i][j], dist[i][k] + dist[k][j]);
                }
            }
        }
        return dist;
    }

    bool bipartite_search(const int node, const int c, std::vector<int>& ret) {
        assert(c == 1 || c == -1); assert(node < ret.size());
        if (ret[node] == -c) { return false; }
        if (ret[node] == c) { return true; }
        assert(ret[node] == 0);
        ret[node] = c;
        for (Edge e : G[node]) {
            if (!bipartite_search(e.to, -c, ret)) { return false; }
        }
        return true;
    }

    std::pair<bool, std::vector<int>> is_bipartite(const int begin, const int end) {
        std::vector<int> ret; ret.resize(end+1, 0);
        for (int i = begin; i <= end; i++) {
            if (ret[i] == 0 && !bipartite_search(i, 1, ret)) {
                return std::pair<bool, std::vector<int>>({false, ret});
            }
        }
        return std::pair<bool, std::vector<int>>({true, ret});
    }

    std::pair<adj_list, std::vector<std::vector<int>>> auxilarity_network() const {
        adj_list Net;
        std::vector<std::vector<int>> Rev;
        Net.resize(node_num);
        Rev.resize(node_num);
        for (int i = 0; i < node_num; i++) {
            for (Edge e : G[i]) {
                Net[i].push_back(e);
                Rev[i].push_back(-1);
            }
        }
        for (int i = 0; i < node_num; i++) {
            for (int j = 0; j < G[i].size(); j++) {
                Edge r; r.to = i; r.cost = 0;
                Rev[i][j] = Net[G[i][j].to].size();
                Net[G[i][j].to].push_back(r);
                Rev[G[i][j].to].push_back(j);
            }
        }
        return std::pair<adj_list, std::vector<std::vector<int>>>({Net, Rev});
    }

    int64_t dfs_increase_path(const int v, const int t, const int64_t f, std::vector<bool>& used, adj_list& Net, const std::vector<std::vector<int>>& Rev) const {
        if (v == t) { return f; }
        used[v] = true;
        for (int i = 0; i < Net[v].size(); i++) {
            Edge &e = Net[v][i];
            if (!used[e.to] && 0 < e.cost) {
                //std::cout << v << " " << e.to << std::endl;
                int d = dfs_increase_path(e.to, t, std::min(f, e.cost), used, Net, Rev);
                //std::cout << v << " " << e.to << " " << d << " " << std::endl;
                if (0 < d) {
                    e.cost -= d;
                    Net[e.to][Rev[v][i]].cost += d;
                    return d;
                }
            }
        }
        return 0;
    }

    std::pair<int64_t, adj_list> max_flow(const int s, const int t) const {
        auto aux = auxilarity_network();
        int64_t flow = 0;
        //std::cout << "flow:" << flow << " " << aux.first[2][0].to << " " << aux.first[2][0].cost << std::endl;
        //std::cout << "flow:" << flow << " " << aux.first[6][0].to << " " << aux.first[6][0].cost << std::endl;
        while (true) {
            std::vector<bool> used; used.resize(node_num, false);
            int64_t f = dfs_increase_path(s, t, std::numeric_limits<int64_t>::max(), used, aux.first, aux.second);
            if (f == 0) { break; }
            flow += f;
            //std::cout << "flow:" << flow << " " << aux.first[2][0].to << " " << aux.first[2][0].cost << std::endl;
            //std::cout << "flow:" << flow << " " << aux.first[6][0].to << " " << aux.first[6][0].cost << std::endl;
            //if (2 < flow) {
            //    break;
            //}
        }
        adj_list ret; ret.resize(node_num);
        for (int i = 0; i < node_num; i++) {
            for (int j = 0; j < G[i].size(); j++) {
                ret[i].push_back(G[i][j]);
                ret[i][j].cost -= aux.first[i][j].cost;
            }
        }
        return std::pair<int64_t, adj_list>({ flow, ret });
    }
};

const int MAX_N = 110;
int H, W;
char a[MAX_N][MAX_N];

Directed_Graph dg = Directed_Graph(MAX_N * MAX_N * 2);

int main(int argc, char **argv) {
    std::cin >> H >> W;

    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            std::cin >> a[i][j];
        }
    }

    //std::cout << "check1" << std::endl;

    int si, sj, ti, tj;

    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            if (a[i][j] == 'o') {
                dg.add_edge(i*W + j, i*W + j + H*W, 1);
            } else if (a[i][j] == 'S') {
                si = i; sj = j;
            } else if (a[i][j] == 'T') {
                ti = i; tj = j;
            }
        }
    }

    if (si == ti || sj == tj) {
        std::cout << -1 << std::endl;
        return 0;
    }

    for (int i = 0; i < H; i++) {
        for (int j = 0; j < W; j++) {
            for (int k = 0; k < W; k++) {
                if (j != k && (a[i][j] == 'o' || a[i][j] == 'S') && (a[i][k] == 'o' || a[i][k] == 'T')) {
                    dg.add_edge(i*W + j + H*W, i*W + k, 1);
                }
            }
        }
    }

    for (int i = 0; i < W; i++) {
        for (int j = 0; j < H; j++) {
            for (int k = 0; k < H; k++) {
                if (j != k && (a[j][i] == 'o' || a[j][i] == 'S') && (a[k][i] == 'o' || a[k][i] == 'T')) {
                    dg.add_edge(j*W + i + H*W, k*W + i, 1);
                }
            }
        }
    }

    //std::cout << si << " " << sj << " " << ti << " " << tj << std::endl;
    //std::cout << "check2" << std::endl;

    auto ret = dg.max_flow(si*W + sj + H*W, ti*W + tj);

    std::cout << ret.first << std::endl;

    
    return 0;
}


Compiler output:
a.cc: In member function 'std::vector<std::vector<long long int> > Directed_Graph::Warshall_Floyd(long long int)':
a.cc:88:41: error: no matching function for call to 'min(__gnu_cxx::__alloc_traits<std::allocator<long long int>, long long int>::value_type&, int64_t&)'
   88 |                 dist[i][e.to] = std::min(dist[i][e.to], e.cost);
      |                                 ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/14/string:51,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44,
                 from /usr/include/c++/14/istream:40,
                 from /usr/include/c++/14/fstream:40,
                 from a.cc:4:
/usr/include/c++/14/bits/stl_algobase.h:233:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  233 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:233:5: note:   template argument deduction/substitution failed:
a.cc:88:41: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int64_t' {aka 'long int'})
   88 |                 dist[i][e.to] = std::min(dist[i][e.to], e.cost);
      |                                 ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  281 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algobase.h:281:5: note:   candidate expects 3 arguments, 2 provided
In file included from /usr/include/c++/14/algorithm:61,
                 from a.cc:8:
/usr/include/c++/14/bits/stl_algo.h:5686:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(initializer_list<_Tp>)'
 5686 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5686:5: note:   candidate expects 1 argument, 2 provided
/usr/include/c++/14/bits/stl_algo.h:5696:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(initializer_list<_Tp>, _Compare)'
 5696 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/14/bits/stl_algo.h:5696:5: note:   template argument deduction/substitution failed:
a.cc:88:41: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   88 |                 dist[i][e.to] = std::min(dist[i][e.to], e.cost);
      |                                 ~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~