T3个点怎么办

rt

吸氧也过不了啊。

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn=1000+10,maxm=1000000+100;
int head[maxn*maxn],mark[maxn][maxn],vis[maxn*maxn];
int s,t,n,m,size=1;
int dx[]={1,-1,1,-1,2,2,-2,-2},dy[]={2,2,-2,-2,1,-1,1,-1};
struct edge
{
    int to,next,cap;
}e[maxm];
void addedge(int u,int v,int val)
{
    e[++size].to=v;e[size].cap=val;e[size].next=head[u];head[u]=size;
    e[++size].to=u;e[size].cap=0;e[size].next=head[v];head[v]=size;
}
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')f=-1;ch=getchar();}
    while(ch<='9'&&ch>='0'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}
    return x*f;
}
int id(int i,int j)
{
    return (i-1)*n+j;
}
int dfs(int u,int f)
{
    if(u==t)
    return f;
    vis[u]=1;
    for(int i=head[u];i;i=e[i].next)
    {
        int to=e[i].to;
        if(!vis[to]&&e[i].cap>0)
        {
            int d=dfs(to,min(e[i].cap,f));
            if(d>0)
            {
                e[i].cap-=d;
                e[i^1].cap+=d;
                return d;
            }
        }
    }
    return 0;
}
int maxflow()
{
    int flow=0;
    while(1)
    {
        memset(vis,0,sizeof(vis));
        int f=dfs(s,inf);
        if(f==0)return flow;
        flow+=f;
    }
}
int main()
{
    n=read(),m=read();
    s=0,t=n*n+1;
    for(int i=1;i<=m;i++)
    {
        int x=read(),y=read();
        mark[x][y]=1;
    }
    for(int i=1;i<=n;i++)
      for(int j=1;j<=n;j++)
        {
          if(mark[i][j])continue;
          int u=id(i,j);
            if((i+j)&1)
            {
              addedge(s,u,1);
              for(int k=0;k<8;k++)
              {
              int x=i+dx[k],y=j+dy[k];
              if(mark[x][y])continue;
              if(x<1||x>n||y<1||y>n)continue;
              int v=id(x,y);
              addedge(u,v,1);
              }

            }
        else addedge(u,t,1);
        }
    printf("%d",n*n-m-maxflow());  
    return 0;
}

裸的ford。