dinic跑二分图匹配是$\sqrt nm$的
by jiangly @ 2019-03-21 18:44:17
@[jiangly](/space/show?uid=149656) 所以这道题虽然不是二分图但是也应该很快吧（试探）
by jiangly @ 2019-03-21 18:46:55
@[破壁人四号](/space/show?uid=55078) 你这显然是个假的ISAP
by ecnerwaIa @ 2019-04-16 17:11:15
@[jiangly](/space/show?uid=149656) 请先看看代码再说话吧
by ecnerwaIa @ 2019-04-16 17:11:36
@[千年之狐_天才](/space/show?uid=54113) 大佬好又见面了（run
by YLWang @ 2019-04-16 18:31:31
@[千年之狐_天才](/space/show?uid=54113) 请问这个为什么有问题（诚意
by YLWang @ 2019-04-16 18:31:48
@[千年之狐_天才](/space/show?uid=54113) /kel
by YLWang @ 2019-04-16 18:32:35
@[破壁人四号](/space/show?uid=55078) 刚在休息，没看到，抱歉
by ecnerwaIa @ 2019-04-16 18:53:37
@[破壁人四号](/space/show?uid=55078) 我可以发一个我写的ISAP
by ecnerwaIa @ 2019-04-16 18:53:54
@[破壁人四号](/space/show?uid=55078)
bzoj 4554
```cpp
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
int n,m,a[52][52],s,t;
inline void read(int &x){
x=0;
char ch=getchar();
while(ch!='*'&&ch!='#'&&ch!='x')ch=getchar();
if(ch=='x')x=1;
else if(ch=='#')x=2;
}
int x[52][52],y[52][52],id,d[6000],to[20000],nxt[20000],flow[20000],tot;
inline void add(int a,int b,int c){
to[++tot]=b;
nxt[tot]=d[a];
d[a]=tot;
flow[tot]=c;
}
inline void ins(int a,int b,int c){
add(a,b,c);add(b,a,0);
}
const int inf=(1<<30);
int dep[6000],num[6000],cur[6000];
queue<int>q;
inline bool bfs(){
memset(dep,0x7f,sizeof(dep));
memcpy(cur,d,sizeof(d));
dep[t]=1;
q.push(t);
while(!q.empty()){
int x=q.front();
q.pop();
for(int i=d[x];i!=-1;i=nxt[i]){
int u=to[i];
if(flow[i^1]&&dep[u]>inf){
dep[u]=dep[x]+1;
q.push(u);
}
}
}
return dep[s]<inf;
}
int pre[6000];
inline int add_flow(){
int now=t,ans=inf;
while(now!=s){
ans=min(ans,flow[pre[now]]);
now=to[pre[now]^1];
}
now=t;
while(now!=s){
flow[pre[now]]-=ans;
flow[pre[now]^1]+=ans;
now=to[pre[now]^1];
}
return ans;
}
inline int ISAP(){
if(!bfs())return 0;
for(int i=s;i<=t;++i)if(dep[i]<inf)num[dep[i]]++;
int now=s,maxflow=0;
while(dep[s]<=t+1){
if(now==t){
maxflow+=add_flow();
now=s;
}
bool have_way=0;
for(int i=cur[now];i!=-1;i=nxt[i]){
int u=to[i];
if(flow[i]&&dep[u]+1==dep[now]){
cur[now]=i;pre[u]=i;
have_way=1;now=u;
break;
}
}
if(!have_way){
if((--num[dep[now]])==0)
return maxflow;
num[++dep[now]]++;
cur[now]=d[now];
if(now!=s)now=to[pre[now]^1];
}
}
return maxflow;
}
//bool f[2500];
int main(){
// freopen("0.in","r",stdin);
memset(d,-1,sizeof(d));
tot=-1;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
read(a[i][j]);
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(a[i][j]!=2){
x[i][j]=++id;
while(j<m&&a[i][++j]!=2){
x[i][j]=id;
}
}
}
}
int xid=id;
for(int i=1;i<=m;++i){
for(int j=1;j<=n;++j){
if(a[j][i]!=2){
y[j][i]=++id;
while(j<n&&a[++j][i]!=2){
y[j][i]=id;
}
}
}
}
for(int i=1;i<=n;++i){
for(int j=1;j<=m;++j){
if(!a[i][j])ins(x[i][j],y[i][j],1);
}
}
s=0;
t=id+1;
// printf("%d\n",id);
// printf("%d\n",tot);
for(int i=1;i<=xid;++i)ins(s,i,1);
for(int i=xid+1;i<=id;++i)ins(i,t,1);
// printf("%d\n",tot);
printf("%d\n",ISAP());
return 0;
}
```
by ecnerwaIa @ 2019-04-16 18:54:31