P3355

Code:

#include <bits/stdc++.h>
using namespace std;
int n,m,s,t,h[9999999],e[9999999],nt[9999999],w[9999999],d[9999999],cnt,x[9999999];
int g[205][205],dx[10] = {1,1,-1,-1,2,2,-2,-2},dy[10] = {2,-2,2,-2,1,-1,1,-1},maxa;
void add(int a,int b,int c)
{
    e[cnt] = b;
    nt[cnt] = h[a];
    h[a] = cnt;
    w[cnt++] = c;
    e[cnt] = a;
    nt[cnt] = h[b];
    h[b] = cnt;
    w[cnt++] = 0;
}
int bfs()
{
    queue<int> q;
    q.push(s);
    memset(d,0,sizeof(d));
    d[s] = 1;
    x[s] = h[s];
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(int i = h[u];i != -1;i = nt[i])
        {
        	if(w[i] != 0 && d[e[i]] == 0)
            {
                x[e[i]] = h[e[i]];
                q.push(e[i]);
                d[e[i]] = d[u] + 1;
                if(e[i] == t)
				{
					return 1;
				}
            }
        }
    }
    return 0;
}
int dinic(int u,int c)
{
    if(u == t)
	{
		return c;
	}
    int ans = c,f,k;
    for(int i = x[u];i != -1;i = nt[i])
    {
    	if(ans == 0)
    	{
    		f = ans;
    		break;
    	}
    	if(w[i] != 0 && d[e[i]] == d[u] + 1)
        {
            k = dinic(e[i],min(w[i],ans));
            if(k == 0)
			{
				d[e[i]] = 0;
			}
            w[i] -= k;
            w[i ^ 1] += k;
            ans -= k;
        }
    }
	x[u] = f;
    return c - ans;
}
int main()
{
	memset(h,-1,sizeof(h));
    int n,m;
    scanf("%d%d",&n,&m);
    t = n * n + 1;
    for(int i = 1;i <= m;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        g[x][y] = 1;
    }
    for(int i = 1;i <= n;i++)
    {
    	for(int j = 1;j <= n;j++)
        {
	      	if(g[i][j] == 0)
	        {
	            if((i + j) & 1)
				{
					add(s,(i - 1) * n + j,1);
				}
	            else
				{
					add((i - 1) * n + j,t,1);
				}
	        }
        }
    }
    for(int i = 1;i <= n;i++)
    {
    	for(int j = 1;j <= n;j++)
        {
        	if((i + j) & 1)
            {
                for(int k = 0;k <= 7;k++)
                {
                	if(i + dx[k] >= 1 && i + dx[k] <= n && j + dy[k] >= 1 && j + dy[k] <= n && g[i + dx[k]][j + dy[k]] == 0)
                    {
                    	add((i - 1) * n + j,(i + dx[k] - 1) * n + j + dy[k],1e9);
                    }
                }
            }
        }
    }
    int sum = 0;
    while(bfs() == 1)
    {
    	sum = dinic(s,1e9);
    	while(sum != 0)
		{
			maxa += sum;
			sum = dinic(s,1e9);
		}
    }
    printf("%d",n * n - m - maxa);
    return 0;
}

求助大佬，请问错在哪？咋搞？

WA了，#5、#8、#11有问题，都是比正确答案少一。

放一组数据（错误的）：

给定的输入输出：
200 4
3 1
3 2
3 3
2 3

19999

我的输出：
19998

急！！！拜谢！！！%%%%%%