Submission #2107498

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>

#define fo(i,j,l) for(int i=j;i<=l;++i)
#define fd(i,j,l) for(int i=j;i>=l;--i)

using namespace std;
typedef long long ll;
const ll N=320,M=N<<1;

int n,m,S,T,inf,limit,point;

int lb[M][N],g[M],d[M];
int flow[M][M];
int vh[M],h[M];

inline char readchar()
{
	char ch=' ';
	for(;ch!='S'&&ch!='T'&&ch!='.'&&ch!='o';ch=getchar());
	return ch;
}

inline int min(int a,int b)
{return a<b?a:b;}

int net(int o,int u)
{
	if(o==T)return u;
	int minh=point+1;
	fo(i,1,g[o]<<1){
		d[o]=d[o]==g[o]?1:d[o]+1;
		int k=lb[o][d[o]];
		if(flow[k][o]){		
			if(h[o]==h[k]+1){
				int uu=net(k,min(u,flow[k][o]));
				if(uu>0){
					flow[k][o]-=uu;
					flow[o][k]+=uu;
					return uu;
				}
				if(h[S]>point)return 0;
			}
			minh=min(minh,h[k]+1);
		}
	}
	--vh[h[o]];
	if(vh[h[o]]==0){
		h[S]=point+1;
		return 0;
	}
	h[o]=minh;
	++vh[h[o]];
	return 0;
}
int main()
{
	cin>>n>>m;
	S=n*m+1,T=S+1,limit=n*m,inf=limit<<1,point=n+m+2;
	fo(i,1,n)fo(l,n+1,m+n){
		char ch=readchar();
		if(ch=='o'){
			flow[i][l]=flow[l][i]=1;
			lb[i][++g[i]]=l; lb[l][++g[l]]=i;
		}
		if(ch=='S'){
			flow[i][S]=inf;	flow[l][S]=inf;
			lb[S][++g[S]]=i; lb[S][++g[S]]=l;
		}
		if(ch=='T'){
			flow[T][i]=inf; flow[T][l]=inf;
			lb[i][++g[i]]=T; lb[l][++g[l]]=T;
		}
	}
	vh[0]=point; ll ans=0;
	while(h[S]<=point)ans+=net(S,inf<<3);
	if(ans>limit)puts("-1");else printf("%lld",ans);
}

Submission Info

Judge Result