【[HEOI2016/TJOI2016]游戏】

据说是网络流棋盘模型了

我们把每一个连续子段都看成一个点，我们先把所有的行上的连续子段找出来给他们编上号，所有列上的连续子段找出来也编上号

现在每个格子都有两个编号了，\(a[i][j]\)表示行所对应的连续子段的编号，\(b[i][j]\)表示列所对应的连续子段的编号

之后我们就需要把这些子段匹配起来就可以了，如果\(map[i][j]=='*'\)，我们就从\(a[i][j]\)向\(b[i][j]\)连边，就可以表达出一个行连续子段只能和一个列连续子段匹配了

代码

#include<cstdio>
#include<cstring>
#include<iostream>
#include<queue>
#include<algorithm>
#define maxn 2505
#define re register
#define LL long long
#define inf 999999999
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
inline int read()
{
    char c=getchar();re int x=0;
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-48,c=getchar();return x;
}
struct E{int v,nxt,w,f;} e[maxn*1000];
int n,m,num=1,S,T,cnt,tot=1;
int head[maxn],cur[maxn],d[maxn];
char map[55][55];
int a[55][55],b[55][55];
inline void add_edge(int x,int y,int z){e[++num].v=y;e[num].nxt=head[x];head[x]=num;e[num].w=z;}
inline void C(int x,int y,int z){add_edge(x,y,z),add_edge(y,x,0);}
inline int BFS()
{
    std::queue<int> q;
    for(re int i=S;i<=tot;i++) cur[i]=head[i],d[i]=0;d[S]=1;d[T]=0;
    q.push(S);
    while(!q.empty())
    {
        int k=q.front();q.pop();
        for(re int i=head[k];i;i=e[i].nxt)
        if(!d[e[i].v]&&e[i].w>e[i].f) d[e[i].v]=d[k]+1,q.push(e[i].v);
    }
    return d[T];
}
int dfs(int x,int now)
{
    if(x==T||!now) return now;
    int flow=0,ff;
    for(re int& i=cur[x];i;i=e[i].nxt)
    if(d[e[i].v]==d[x]+1)
    {
        ff=dfs(e[i].v,min(now,e[i].w-e[i].f));
        if(!ff) continue;
        now-=ff,flow+=ff;
        e[i].f+=ff,e[i^1].f-=ff;
        if(!now) break;
    }
    return flow;
}
int main()
{
    n=read(),m=read();T=n*m;
    for(re int i=1;i<=n;i++) 
        for(re int j=1;j<=m;j++) std::cin>>map[i][j];
    for(re int i=1;i<=n;i++)
    {
        int sz=0;
        for(re int j=1;j<=m;j++) 
        if(map[i][j]=='#') {if(sz) C(S,tot,1),tot++;sz=0;}
            else if(map[i][j]=='*') sz++,a[i][j]=tot;
        if(!sz) continue;
        C(S,tot,1);tot++;
    }
    for(re int j=1;j<=m;j++)
    {
        int sz=0;
        for(re int i=1;i<=n;i++)
        if(map[i][j]=='#') {if(sz) C(tot,T,1),tot++;sz=0;}
            else if(map[i][j]=='*') sz++,b[i][j]=tot;
        if(!sz) continue;
        C(tot,T,1);tot++;
    }
    for(re int i=1;i<=n;i++)
        for(re int j=1;j<=m;j++) if(map[i][j]=='*') C(a[i][j],b[i][j],1);
    int ans=0;
    while(BFS()) 
        ans+=dfs(S,inf);
    printf("%d\n",ans);
    return 0;
}