\(\text{Problem}:\)[ARC074D] Lotus Leaves
\(\text{Solution}:\)editorial
记点 \((i,j)\) 表示一条连接 \(i\) 和 \(j+H\) 的双向边，那么，所有满足 \(s_{i,j}\) 不是 . 的 \((i,j)\) 就构建出了一张图。那么题目转化为：在这个图上删去一些边，使得 \(S\) 和 \(T\) 不连通。
首先，当 \(S\) 和 \(T\) 的横坐标或纵坐标相等时，答案显然为 \(-1\)。否则，我们构建出这个图，对于 \((i,j)\)：
- \(S=(i,j)\)，从源点向这个 \(i\) 和 \(j+H\) 分别连一条流量为 \(INF\) 的边。
- \(T=(i,j)\)，从 \(i\) 和 \(j+H\) 分别连一条流量为 \(INF\) 的边。
o\(=(i,j)\)，那么 \(i,j+H\) 之间连一条流量为 \(1\) 的双向边。
那么答案即为这张图的最小割，求出最大流即可。
\(\text{Code}:\)
#include <bits/stdc++.h>
#pragma GCC optimize(3)
//#define int long long
#define ri register
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define is insert
#define es erase
using namespace std; const int N=210, INF=1e9;
inline int read()
{
int s=0, w=1; ri char ch=getchar();
while(ch<'0'||ch>'9') { if(ch=='-') w=-1; ch=getchar(); }
while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^48), ch=getchar();
return s*w;
}
int H,W,sx,sy,tx,ty;
char s[N][N];
int S,T,dis[N];
int head[N],maxE,cur[N]; struct Edge { int nxt,to,rdis; }e[N*N*2];
inline void Add(int u,int v,int w) { e[maxE].nxt=head[u]; head[u]=maxE; e[maxE].to=v; e[maxE].rdis=w; maxE++; }
inline bool BFS()
{
memset(dis,-1,sizeof(dis));
queue<int> Q;
dis[S]=0, Q.push(S);
while(!Q.empty())
{
int x=Q.front(); Q.pop();
for(ri int i=head[x];~i;i=e[i].nxt)
{
int v=e[i].to;
if(dis[v]==-1&&e[i].rdis>0)
{
dis[v]=dis[x]+1;
Q.push(v);
}
}
}
return ~dis[T];
}
int DFS(int x,int pro)
{
if(x==T) return pro;
int res,p; res=p=0;
for(ri int &i=cur[x];~i;i=e[i].nxt)
{
int v=e[i].to;
if(dis[v]==dis[x]+1&&e[i].rdis>0)
{
p=DFS(v,min(pro,e[i].rdis));
if(!p) continue;
pro-=p, res+=p;
e[i].rdis-=p, e[i^1].rdis+=p;
if(!pro) break;
}
}
if(!res) dis[x]=-1;
return res;
}
signed main()
{
H=read(), W=read(), T=H+W+1;
for(ri int i=1;i<=H;i++)
{
scanf("%s",s[i]+1);
for(ri int j=1;j<=W;j++)
{
if(s[i][j]=='S') sx=i, sy=j;
if(s[i][j]=='T') tx=i, ty=j;
}
}
if(sx==tx || sy==ty) return puts("-1")&0;
memset(head,-1,sizeof(head));
Add(S,sx,INF), Add(sx,S,0);
Add(S,sy+H,INF), Add(sy+H,S,0);
Add(tx,T,INF), Add(T,tx,0);
Add(ty+H,T,INF), Add(T,ty+H,0);
for(ri int i=1;i<=H;i++)
for(ri int j=1;j<=W;j++)
if(s[i][j]=='o') Add(i,j+H,1), Add(j+H,i,0), Add(j+H,i,1), Add(i,j+H,0);
int Ans=0;
while(BFS())
{
for(ri int i=0;i<=T;i++) cur[i]=head[i];
Ans+=DFS(S,INF);
}
printf("%d\n",Ans);
return 0;
}