【二分圖最大比對】BZOJ4554 [Tjoi2016&Heoi2016]遊戲

題面在這裡

典型的二分圖最大比對……

隻需要把每行/每列的空隙看作點

空地就看作空隙之間的聯系

建邊刷即可

這裡用了時間戳标記，新姿勢Get

示例程式：

#include<cstdio>
#include<cstring>
inline char fstchar(){
    char ch=getchar();while (ch!='*'&&ch!='#'&&ch!='x') ch=getchar();
    return ch;
}

const int maxn=,maxe=;
int n,m,h[][],z[][],Tim=;
char a[][];
int tot,lnk[maxn],son[maxe],nxt[maxe];
inline void add(int x,int y){
    son[++tot]=y;nxt[tot]=lnk[x];lnk[x]=tot;
}
int vis[maxn],con[maxn];
bool find(int x){
    if (vis[x]==Tim) return ;
    vis[x]=Tim;
    for (int j=lnk[x];j;j=nxt[j]){
        int k=con[son[j]];con[son[j]]=x;
        if (!k||find(k)) return ;
        con[son[j]]=k;
    }
    return ;
}
int main(){
    scanf("%d%d",&n,&m);
    memset(a,'#',sizeof(a));
    for (int i=;i<=n;i++){
        a[i][]=fstchar();
        for (int j=;j<=m;j++) a[i][j]=getchar();
    }
    int N=;
    for (int i=;i<=n;i++)
     for (int j=;j<=m;j++){
        if (a[i][j-]=='#') N++;
        if (a[i][j]=='*') h[i][j]=N;
     }
    int maxH=N;
    for (int j=;j<=m;j++)
     for (int i=;i<=n;i++){
        if (a[i-][j]=='#') N++;
        if (a[i][j]=='*') z[i][j]=N;
     }
    for (int i=;i<=n;i++)
     for (int j=;j<=m;j++)
      if (a[i][j]=='*') add(h[i][j],z[i][j]);
    int ans=;
    for (int i=;i<=maxH;i++)
     Tim++,ans+=find(i);
    printf("%d",ans);
    return ;
}