Submission #2115356

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define efo(i,q) for(int i=A[q];i;i=B[i][0])
using namespace std;
const int N=10500,INF=1e9;
int read(int &n)
{
	char ch=' ';int q=0,w=1;
	for(;(ch!='-')&&((ch<'0')||(ch>'9'));ch=getchar());
	if(ch=='-')w=-1,ch=getchar();
	for(;ch>='0' && ch<='9';ch=getchar())q=q*10+ch-48;n=q*w;return n;
}
int m,n,ans;
int S,T;
int B[2*N][3],A[N],B0=1;
int Hv[N],H[N];
void link(int q,int w,int e,int e1=1)
{
	B[++B0][0]=A[q],A[q]=B0,B[B0][1]=w,B[B0][2]=e;
	B[++B0][0]=A[w],A[w]=B0,B[B0][1]=q,B[B0][2]=e1;
}
int aug(int q,int e)
{
	if(q==T)return e;
	int mi=T+10;
	efo(i,q)if(B[i][2])
	{
		if(H[B[i][1]]+1==H[q])
		{
			int t=aug(B[i][1],min(e,B[i][2]));
			if(t)
			{
				B[i][2]-=t;
				B[i^1][2]+=t;
				return t;
			}
		}
		mi=min(mi,H[B[i][1]]);
	}
	if(!(--Hv[H[q]]))H[S]=T+10;
	++Hv[H[q]=mi+1];
	return 0;
}
int main()
{
	int q,w;
	read(n),read(m);
	S=0,T=n+m+1;
	fo(i,1,n)
	{
		char ch=' ';
		for(;ch!='.'&&ch!='o'&&ch!='S'&&ch!='T';ch=getchar());
		fo(j,1,m)
		{
			if(ch=='o')link(i,j+n,1);
			if(ch=='S')link(S,j+n,INF,0),link(S,i,INF,0);
			if(ch=='T')link(j+n,T,INF,0),link(i,T,INF,0);
			ch=getchar();
		}
	}
	for(Hv[0]=T+1;H[0]<T;ans+=aug(S,INF));
	if(ans>=INF)printf("-1\n");
		else printf("%d\n",ans);
	return 0;
}

Submission Info

Judge Result