题目传送门:http://cojs.tk/cogs/problem/problem.php?pid=746
好吧,我承认我看的是题解……
推荐这家的题解:https://oi.men.ci/cogs-746/
自己来说的话,就是搞一搞二分图?
染色之后,发现有冲突的点都在不同的集合内
于是连边,跑最小割即可
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 40000+9; const int M = N*10; const int L = 200+9; const int INF = 10000000; int head[N],nxt[M],to[M],flow[M],cur[N],dis[N]; int n,m,mat[L][L],vout,S,T; int dx[]={0,2,1,-1,-2,-2,-1,1,2}; int dy[]={0,1,2,2,1,-1,-2,-2,-1}; queue<int> que; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } #define id(x,y) ((x)+((y)-1)*n) inline void Add_Edge(int u, int v, int f){ static int TT = 1; to[++TT] = v; nxt[TT] = head[u]; head[u] = TT; flow[TT] = f; to[++TT] = u; nxt[TT] = head[v]; head[v] = TT; flow[TT] = 0; } inline bool BFS(){ memset(dis,-1,sizeof(dis)); dis[S] = 0; que.push(S); while (!que.empty()) { int w = que.front(); que.pop(); for (int i=head[w];i;i=nxt[i]) if (flow[i] && !~dis[to[i]]) dis[to[i]] = dis[w] + 1, que.push(to[i]); } return ~dis[T]; } int DFS(int w, int f) { if (w == T) return f; else { int ret = 0; for (int &i=cur[w];i;i=nxt[i]) if (flow[i] && dis[to[i]] == dis[w] + 1) { int tmp = DFS(to[i], min(f, flow[i])); ret += tmp; f -= tmp; flow[i] -= tmp; flow[i^1] += tmp; if (!f) break; } return ret; } } inline int Dinic(){ int ret = 0; while (BFS()) { memcpy(cur,head,sizeof(head)); ret += DFS(S,INF); } return ret; } int main(){ freopen("knight.in","r",stdin); freopen("knight.out","w",stdout); n = read(); m = read(); S = 0; T = N-1; vout = n*n; for (int i=1,x,y;i<=m;i++) x = read(), y = read(), mat[x][y] = 1, vout--; for (int j=1;j<=n;j++) for (int i=1;i<=n;i++) if (!mat[i][j]) if ((i+j)&1) { Add_Edge(S,id(i,j),1); for (int k=1,x,y;k<=8;k++) { x = i + dx[k]; y = j + dy[k]; if (1 <= x && x <= n && 1 <= y && y <= n && !mat[x][y]) Add_Edge(id(i,j),id(x,y),INF); } } else Add_Edge(id(i,j),T,1); vout -= Dinic(); printf("%d\n",vout); return 0; }