Submission #5915181

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define _for(i,j,N) for(int i = (j);i < (N);i++)
#define _rep(i,j,N) for(int i = (j);i <= (N);i++)
#define ALL(x) x.begin(),x.end()
#define pb push_back
#define mk make_pair

typedef long long LL;
typedef pair<int,int> pi;

template<typename T>
ostream& operator<<(ostream& os,const vector<T>& v) {
    _for(i,0,v.size()) os << v[i] << " ";
    return os;
}

template<typename T>
ostream& operator<<(ostream& os,const set<T>& v){
    for(typename set<T>::iterator it = v.begin();it != v.end();it++)
    os << *it <<" ";
    return os;
}

template<typename T1,typename T2>
ostream& operator<<(ostream& os,const pair<T1,T2>& v){
    os << v.first <<" "<<v.second<<endl;
    return os;
}

const int maxn= 205;
const int maxm = 3e4+ 5;
const int INF = 1e4+5;



struct Dinic{
    struct Edge{
        int from,to,cap,flow;
        Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){;}
    };
    int n,m,s,t;
    vector<Edge> edges;
    vector<int> G[maxn];
    bool vis[maxn];
    int d[maxn];
    int cur[maxn];

    void AddEdge(int from,int to,int cap){
        edges.push_back(Edge(from,to,cap,0));
        edges.push_back(Edge(to,from,0,0));
        m = edges.size();
        G[from].push_back(m-2);
        G[to].push_back(m-1);
    }


    bool BFS(){
        memset(vis,0,sizeof(vis));
        queue<int> Q;
        Q.push(s);
        d[s] = 0;
        vis[s] = 1;
        while(!Q.empty()){
            int x = Q.front();Q.pop();
            _for(i,0,G[x].size()){
                Edge e = edges[G[x][i]];
                if(!vis[e.to] && e.cap > e.flow){
                    vis[e.to] = 1;
                    d[e.to] = d[x]+1;
                    Q.push(e.to);
                }
            }
        }
        return vis[t];
    }

    int DFS(int x,int a){
        if(x == t || a == 0) return a;
        int flow = 0,f;
        for(int &i = cur[x];i < G[x].size();i++){
            Edge &e = edges[G[x][i]];
            if(d[x] + 1 == d[e.to] && (f = DFS(e.to,min(a,e.cap-e.flow))) > 0){
                e.flow += f;
                edges[G[x][i]^1].flow -= f;
                flow += f;
                a -= f;
                if(a == 0) break;
            }
        }
        return flow;
    }

    int Maxflow(int s,int t){
        this->s = s;this->t = t;
        int flow = 0;
        while(BFS()){
            memset(cur,0,sizeof(cur));
            flow += DFS(s,INF);
            //cout << flow << endl;
        }
        return flow;
    }

};

int H,W;
char G[maxn][maxn];

int stx,sty,edx,edy;

int ans;

int get_x(int x) {return x+1;}
int get_y(int y) {return H+1+y;}

int main()
{
    cin >> H >> W;
    getchar();
    _for(i,0,H){
        fgets(G[i],maxn,stdin);
    }

     Dinic maxf;
     //maxf.init(maxn);
     int ed = H+W+1;

    _for(i,0,H){
        _for(j,0,W){
            if(G[i][j] == 'S'){
                maxf.AddEdge(0,get_x(i),INF);
                maxf.AddEdge(0,get_y(j),INF);
                stx = i;sty = j;
            }
            else if(G[i][j] == 'T'){
                maxf.AddEdge(get_x(i),ed,INF);
                maxf.AddEdge(get_y(j),ed,INF);
                edx = i;edy = j;
            }
            else if(G[i][j] == 'o'){
                maxf.AddEdge(get_x(i),get_y(j),1);
                maxf.AddEdge(get_y(j),get_x(i),1);
            }
        }
    }


    if(stx == edx || sty == edy){
        printf("-1\n");
        return 0;
    }

    cout << maxf.Maxflow(0,ed) << endl;

    return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:124:31: warning: ignoring return value of ‘char* fgets(char*, int, FILE*)’, declared with attribute warn_unused_result [-Wunused-result]
         fgets(G[i],maxn,stdin);
                               ^

Judge Result