这咋都能对啊

P3355 骑士共存问题

peterwuyihong @ 2021-04-03 11:59:13

#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 250*250
#define maxm 250*250*16
using namespace std;
int n,k,x,y,tot=1,ans;bool Map[250][250];
int head[maxn],Next[maxm],ver[maxm];
short dx[8]={1,1,2,2,-1,-1,-2,-2};
short dy[8]={2,-2,1,-1,2,-2,1,-1};
int query[maxn],cnt;
bool v[maxn];int match[maxn];
void add(int x,int y)
{
    ver[++tot]=y;
    Next[tot]=head[x];
    head[x]=tot;
}
bool dfs(int x)
{
    for(int i=head[x],y;i;i=Next[i])
    if(!v[y=ver[i]])
    {
        v[y]=1;
        if(match[y]==0||dfs(match[y]))
        {
            match[y]=x;
            return 1;   
        }
    }
    return 0;
}
int main()
{
    scanf("%d %d",&n,&k);
    for(int i=1;i<=k;i++)
    {
        scanf("%d %d",&x,&y);
        Map[x][y]=1;
    }
    for(int i=1;i<=n;i++)
    for(int j=1;j<=n;j++)
    if(!Map[i][j])
    {
        query[++cnt]=i*250+j;
        for(int Case=0;Case<4;Case++)
        {
            int tx=i+dx[Case],ty=j+dy[Case];
            if(Map[tx][ty])continue;
            if(tx<1||ty<1||tx>n||ty>n)continue;
        //  printf("Link (%d,%d) and (%d,%d)\n",i,j,tx,ty);
            add(tx*250+ty,i*250+j);
            add(i*250+j,tx*250+ty);
        }
    }
    for(int i=1;i<=cnt;i++)
    memset(v,0,sizeof v),ans+=dfs(query[i]);
    printf("%d\n",n*n-k-(ans>>1));
}
```pascal for(int Case=0;Case<4;Case++) ``` 应改为 ```cpp for(int Case=0;Case<8;Case++) ```

by —只书虫仔 @ 2021-04-03 12:06:19

??!


by Remake_ @ 2021-04-03 12:14:53

这为啥不能对啊


by peterwuyihong @ 2021-04-04 17:36:30

@Miracle_Creator 这咋对啊


by peterwuyihong @ 2021-04-04 17:52:39

明白了,此贴结


|