Submission #2575256

---

Source Code Expand

#include <cstdio>
#include <cstring>
#include <string>
#include <iostream>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#define INF 10000000000000000LL

using namespace std;
typedef long long int ll;

struct edge {int to; long long int cap; int rev;} ;
 
vector<edge> G[20002];
int level[20002];
int iter[20002];
 
void add_edge(int from, int to, long long int cap){
	edge e;
	e.to=to, e.cap=cap, e.rev=G[to].size();
	G[from].push_back(e);
	e.to=from, e.cap=0, e.rev=G[from].size()-1;
	G[to].push_back(e);
}
 
void bfs(int s){
	memset(level, -1, sizeof(level));
	queue<int> que;
	level[s]=0;
	que.push(s);
	while(!que.empty()){
		int v=que.front();
		que.pop();
		for(int i=0; i<G[v].size(); i++){
			edge e=G[v][i];
			if(e.cap>0 && level[e.to]<0){
				level[e.to]=level[v]+1;
				que.push(e.to);
			}
		}
	}
}
 
long long int dfs(int v, int t, long long int f){
	if(v==t) return f;
	for(int &i=iter[v]; i<G[v].size(); i++){
		edge &e=G[v][i];
		if(e.cap>0 && level[v]<level[e.to]){
			long long int d=dfs(e.to, t, min(f, e.cap));
			if(d>0){
				e.cap-=d;
				G[e.to][e.rev].cap+=d;
				return d;
			}
		}
	}
	return 0;
}
 
long long int max_flow(int s, int t){
	long long int flow=0;
	while(1){
		bfs(s);
		if(level[t]<0) return flow;
		memset(iter, 0, sizeof(iter));
		long long int f;
		while((f=dfs(s, t, INF))>0){
			flow+=f;
		}
	}
}

int main()
{
	int h, w;
	scanf("%d %d", &h, &w);
	char a[100][100];
	for(int i=0; i<h; i++){
		scanf("%s", a[i]);
	}
	int s, t, xs, ys, xt, yt;
	for(int i=0; i<h; i++){
		for(int j=0; j<w; j++){
			if(a[i][j]=='S') s=2*(i*w+j)+1, xs=i, ys=j;
			if(a[i][j]=='T') t=2*(i*w+j), xt=i, yt=j;
			if(a[i][j]=='o' || a[i][j]=='S'){
				if(a[i][j]=='o') add_edge(2*(i*w+j), 2*(i*w+j)+1, 1);
				for(int k=0; k<w; k++){
					if(k!=j && (a[i][k]=='o' || a[i][k]=='T')){
						add_edge(2*(i*w+j)+1, 2*(i*w+k), 1);
					}
				}
				for(int k=0; k<h; k++){
					if(k!=i && (a[k][j]=='o' || a[k][j]=='T')){
						add_edge(2*(i*w+j)+1, 2*(k*w+j), 1);
					}
				}
			}
		}
	}
	if(xs==xt || ys==yt){
		printf("%d\n", -1);
		return 0;
	}
	printf("%lld\n", max_flow(s, t));
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:83:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d", &h, &w);
                        ^
./Main.cpp:86:20: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", a[i]);
                    ^

Judge Result