记录编号	389343	评测结果	AAAAAAAAAA
题目名称	[网络流24题] 骑士共存	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.669 s
提交时间	2017-03-31 09:48:51	内存使用	1.40 MiB

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cstdarg>
#include <list>
#include <queue>
#include <vector>
#include <algorithm>
#include <cctype>
using namespace std;
#define MAXN 40233
namespace IO{
  char buf[1<<18], *fs, *ft;
  inline char readc(){
    return (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<18,stdin)),fs==ft)?EOF:*fs++;
  }
  inline int readint(){
    char c; int r;
    while(c = readc()){if(c >= '0' && c <= '9'){r = c^0x30;break;}}
    while(isdigit(c = readc()))r = (r<<3)+(r<<1)+(c^0x30);
    return r;
  }
  inline int read_string(char *str){
    int len = 1;char c;
    while(!isalpha(c = readc()));str[0] = c;
    while(isalpha(c = readc()))str[len++] = c;
    str[len] = 0;
    return len;
  }
};using IO::read_string; using IO::readint;
struct edge{
  int from, to, rem;
}; vector<edge> edges;
vector<int> G[MAXN];
void addedge(int u, int v, int f){
  edges.push_back((edge){u, v, f});
  edges.push_back((edge){v, u, 0});
  int k = edges.size();
  G[u].push_back(k-2); G[v].push_back(k-1);
}
int dist[MAXN];
int cure[MAXN];
bool vis[MAXN];
int s, t;
bool bfs(){
  memset(vis, false, sizeof(vis));
  queue<int> q;
  q.push(s);
  vis[s] = true, dist[s] = 0;
  while(!q.empty()){
    int u = q.front(); q.pop();
    for(int i = 0; i < G[u].size(); i++){
      edge &e = edges[G[u][i]];
      if(e.rem > 0 && !vis[e.to]){
        vis[e.to] = true;
        q.push(e.to);
        dist[e.to] = dist[u]+1;
      }
    }
  }
  return vis[t];
}
int dfs(int u, int f){
  if(u == t || !f)return f;
  int tot = 0;
  for(int &i = cure[u]; i < G[u].size(); i++){
    edge &e = edges[G[u][i]];
    int next;
    if(dist[e.to] == dist[u]+1 && (next = dfs(e.to, min(f, e.rem))) > 0){
      f -= next, tot += next, edges[G[u][i]^1].rem += next, e.rem -= next;
      if(!f)break;
    }
  }
  return tot;
}
int maxflow(){
  int f = 0;
  while(bfs())memset(cure, 0, sizeof(cure)),
    f += dfs(s, 0x7fffffff);return f;
}
bool rect[201][201];
int n, m;
inline int getv(int x, int y){
  return (x-1)*n+y;
}
int dx[] = {-2,-1,1,2,2,1,-1,-2};
int dy[] = {1,2,2,1,-1,-2,-2,-1};
int main(){
  freopen("knight.in", "r", stdin);
  freopen("knight.out", "w", stdout);
  n = readint(); m = readint();
  while(m--){
    int x = readint(); int y = readint();
    rect[x][y] = true;
  }
  int tot = 0;
  s = 0, t = n*n+1;
  for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++){
    if(rect[i][j])continue; tot++;
    if((i+j)&1)addedge(getv(i, j), t, 1); //white
    else addedge(s, getv(i, j), 1); //black
  }
  for(int i = 1; i <= n; i++)for(int j = 1; j <= n; j++){
    if((i+j)&1 || rect[i][j])continue;
    for(int k = 0; k < 8; k++){
      int nx = i+dx[k], ny = j+dy[k];
      if(!(nx < 1 || nx > n || ny < 1 || ny > n || rect[nx][ny]))//continue;
        addedge(getv(i, j), getv(nx, ny), 0x7fffffff);
    }
  }
  printf("%d\n", tot-maxflow());
  return 0;
}