Description
众所周知，二高是一个生态环境非常好的学校。
二高的河里面有一片水域种了荷花。这片水域被划分为了R行C列的网格图，其中有一些格子上有荷叶，有一些格子上没有。
现在有一只青蛙站在标记了S的荷叶上。青蛙想要到达标记了T的荷叶上。由于青蛙的姿势水平不高，而且也没有香港记者的速度，不能轻功水上漂，它只能从当前所处的荷叶跳到同一行或者同一列的其它荷叶上。
ZJT看到这只青蛙，感觉到了时间的流逝正在慢慢加速，他心想，如果让青蛙到达了T荷叶，那么可怕的事情——+1s就会发生，而作为二高法学姿势水平最高的人，他不能让这样的事情发生。由于ZJT姿势水平高超，所以他可以使一些荷叶像轮子一样转动起来，这样青蛙就没办法跳上去了。不过ZJT并不想使青蛙遭受灭顶之灾，而且他的能力也有一定限制，所以他想知道，如果只转动除了S和T之外的荷叶，那么他最少转动多少荷叶，可以使青蛙无法到达T荷叶？
Input
第一行是两个正整数R,C
接下来是一个R∗C的字符矩阵，第i行第j个字符为ai,j
若ai,j==′.′，那么这个格子是水面
若ai,j==′o′，那么这个格子是一片荷叶
若ai,j==′S′或者′T′，那么这个格子是标记了S,T的荷叶
Output
如果ZJT无法阻止+1s，那么输出-1
否则输出他最少需要转动的荷叶的个数
Solution
网络流没有时间复杂度 就很容易想到每个荷叶拆一下点，流量为一。 直接两两连边复杂度起飞，每行每列开一个点，然后行列的点跟该行列的荷叶连边就行了。
然后最小割就完事了。
Code
#include<bits/stdc++.h>
using namespace std
;
#define inf 0x7fffffff
struct data
{
int v
,w
,nxt
;
}e
[2000010];
int head
[30010],cnt
;
void add(int u
,int v
,int w
){
e
[cnt
].v
=v
;
e
[cnt
].w
=w
;
e
[cnt
].nxt
=head
[u
];
head
[u
]=cnt
;
cnt
++;
}
inline void ad(int u
,int v
,int w
){
add(u
,v
,w
);
add(v
,u
,0);
}
int n
,m
;
int ans
;
int dis
[30010];
int cur
[30010];
queue
<int>q
;
int s
,t
;
void init(){
cnt
=0,memset(head
,-1,sizeof(head
));
}
int bfs(){
for(int i
=s
;i
<=t
;i
++)
dis
[i
]=-1,cur
[i
]=head
[i
];
while(!q
.empty()) q
.pop();
dis
[s
]=0;
q
.push(s
);
while(!q
.empty()){
int u
=q
.front(); q
.pop();
for(int i
=head
[u
];i
!=-1;i
=e
[i
].nxt
){
int v
=e
[i
].v
;
if(dis
[v
]==-1&&e
[i
].w
){
dis
[v
]=dis
[u
]+1;
q
.push(v
);
}
}
}
return dis
[t
]!=-1;
}
int dfs(int u
,int exp
){
if(u
==t
) return exp
;
int flow
=0,tmp
= 0;
for(int i
=cur
[u
];i
!=-1;i
=e
[i
].nxt
){
cur
[u
]=i
;
int v
=e
[i
].v
;
if(dis
[v
]==dis
[u
]+1&&e
[i
].w
){
tmp
=dfs(v
,min(exp
,e
[i
].w
));
if(!tmp
) continue;
exp
-=tmp
;
flow
+=tmp
;
e
[i
].w
-=tmp
;
e
[i
^1].w
+=tmp
;
if(!exp
) break;
}
}
return flow
;
}
char ch
[110];
int a
[110][110],tot
,st
,ed
;
int main(){
init();
scanf("%d%d",&n
,&m
); tot
=n
+m
;
for(int i
=1;i
<=n
;i
++){
scanf("%s",ch
+1);
for(int j
=1;j
<=m
;j
++){
if(ch
[j
]!='.'){
a
[i
][j
]=++tot
;
ad(a
[i
][j
],++tot
,1);
}
if(ch
[j
]=='S') st
=a
[i
][j
];
if(ch
[j
]=='T') ed
=a
[i
][j
];
}
}
s
=0,t
=tot
+1;
ad(s
,st
+1,inf
);
ad(ed
,t
,inf
);
for(int i
=1;i
<=n
;i
++)
for(int j
=1;j
<=m
;j
++)
if(a
[i
][j
]){
ad(i
,a
[i
][j
],inf
);
ad(a
[i
][j
]+1,i
,inf
);
}
for(int i
=1;i
<=m
;i
++)
for(int j
=1;j
<=n
;j
++)
if(a
[j
][i
]){
ad(n
+i
,a
[j
][i
],inf
);
ad(a
[j
][i
]+1,n
+i
,inf
);
}
while(bfs()) ans
+=dfs(s
,inf
);
printf("%d",ans
==inf
?-1:ans
);
}
