Tyvj1053 棋盘覆盖


二分图最大匹配裸题,甚至不需要建边,直接在棋盘上搜索即可,给点附上编号$n*i+j$

#include<bits/stdc++.h>
using namespace std;
const int maxn=10000;
inline int read()
{
    int x=0,t=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')t=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
    return x*t;
}
int n,m,ans=0;
int pan[105][105],match[maxn],vis[maxn];
int dx[]={1,-1,0,0};
int dy[]={0,0,1,-1};
bool dfs(int u)
{
    int x=u/n,y=u%n;
    for(int i=0;i<4;i++)
    {
        int x1=x+dx[i],y1=y+dy[i];
        int v=x1*n+y1;
        if(x1<1||x1>n||y1<1||y1>n) continue;
        if(vis[v]||pan[x1][y1]) continue;
        vis[v]=1;
        if(!match[v]||dfs(match[v]))
        {
            match[v]=u;
            return true;
        }
    }
    return false;
}
int main()
{
    n=read(),m=read();
    memset(pan,0,sizeof(pan));
    for(int i=1;i<=m;i++)
    {
        int x,y;
        x=read(),y=read();
        pan[x][y]=1;
    }
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
        {
            if(!pan[i][j]&&((i+j)%2))
            {
                memset(vis,0,sizeof(vis));
                if(dfs(i*n+j)) ans++;
            }
        }
    printf("%d\n",ans);    
    return 0;
}

文章作者: songhn
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 songhn !
评论
 上一篇
POJ1741 Tree POJ1741 Tree
初学点分治,挂一个博客 需要注意的地方在于找树的重心的过程,因为我们对一个树进行分治,所以容斥的时候的n不能是总点数,而应该分成两个函数,一个dfssize和disroot,统计出每个点儿子最多的节点,然后找根的过程中这样更新$maxv[u
2019-07-06
下一篇 
POJ1201Intervals POJ1201Intervals
这是一道差分约束,可以考虑前缀和,对于一个区间$[a_i,b_i]$要使选取数字超过$c_i$,可以得出不等式$s[b_i]-s[a_i-1]\geq c_i$,当然这样的限制还不够,我们要保证它的结果有意义,对于每一个$k$,都存在这样两
2019-07-05
  目录