2 条题解

  • 0
    @ 2025-10-8 16:57:19
    #include<bits/stdc++.h>
    using namespace std;
    int dx[8]={-2, -1, 1, 2, -2, -1, 1, 2};
    int dy[8]={-1, -2, -2, -1, 1, 2, 2, 1};
    struct edge{int x, y, pre;}a[210000];int alen, last[11000];
    void ins(int x, int y) {a[++alen]={x, y, last[x]}; last[x]=alen;}
    bool v[110][110]; 
    int n, m, t, match[110000], chw[110000], tsp;
    bool dfs(int x)
    {
        for(int k=last[x];k;k=a[k].pre)
        {
            int y=a[k].y;
            if(chw[y]!=tsp)
            {
                chw[y]=tsp;
                if(!match[y]||dfs(match[y]))
                {
                    match[y]=x;
                    return true;
                }
            }
        }
        return false;
    }
    int main()
    {
        scanf("%d%d%d", &n, &m, &t);
        memset(v,0,sizeof(v));
        for(int i=1,x,y;i<=t;i++)scanf("%d%d", &x, &y),v[x][y]=1;
    
        for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(!v[i][j]&&(i+j)%2)
            for(int k=0;k<8;k++)
            {
                int x=i+dx[k];
                int y=j+dy[k];
                if(x>0&&y>0&&x<=n&&y<=m&&!v[x][y])ins((i-1)*m+j, (x-1)*m+y);
            }
    
        int ans=0;
        for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if((i+j)%2&&!v[i][j])
        {
            tsp++;
            if(dfs((i-1)*m+j)) ans++;
        }
        printf("%d", n*m-t-ans);
        return 0;
    }
    
    • 0
      @ 2025-10-8 16:57:09
      #include<bits/stdc++.h>
      using namespace std;
      int dx[8]={-2, -1, 1, 2, -2, -1, 1, 2};
      int dy[8]={-1, -2, -2, -1, 1, 2, 2, 1};
      struct edge{int x, y, pre;}a[210000];int alen, last[11000];
      void ins(int x, int y) {a[++alen]={x, y, last[x]}; last[x]=alen;}
      bool v[110][110]; 
      int n, m, t, match[110000], chw[110000], tsp;
      bool dfs(int x)
      {
          for(int k=last[x];k;k=a[k].pre)
          {
              int y=a[k].y;
              if(chw[y]!=tsp)
              {
                  chw[y]=tsp;
                  if(!match[y]||dfs(match[y]))
                  {
                      match[y]=x;
                      return True;
                  }
              }
          }
          return False;
      }
      int main()
      {
          scanf("%d%d%d", &n, &m, &t);
          memset(v,0,sizeof(v));
          for(int i=1,x,y;i<=t;i++)scanf("%d%d",&x,&y),v[x][y]=1;
      
          for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if(!v[i][j]&&(i+j)%2)
              for(int k=0;k<8;k++)
              {
                  int x=i+dx[k];
                  int y=j+dy[k];
                  if(x>0&&y>0&&x<=n&&y<=m&&!v[x][y])ins((i-1)*m+j, (x-1)*m+y);
              }
      
          int ans=0;
          for(int i=1;i<=n;i++)for(int j=1;j<=m;j++)if((i+j)%2&&!v[i][j])
          {
              tsp++;
              if(dfs((i-1)*m+j)) ans++;
          }
          printf("%d", n*m-t-ans);
          return 0;
      }
      • 1

      *【二分图:最大独立集(难度:5)】骑士放置

      信息

      ID
      1467
      时间
      2000ms
      内存
      64MiB
      难度
      8
      标签
      递交数
      164
      已通过
      25
      上传者