Dinic 最后一个点 TLE 求助

#include<bits/stdc++.h>
#define pos(i, j) ((i-1)*nn+j)
#define int long long
using namespace std;
inline int read(){
    int x = 0, f = 1;
    char ch = getchar();
    while(!isdigit(ch)){
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(isdigit(ch)){
        x = (x<<1) + (x<<3) + (ch^48);
        ch = getchar();
    }
    return x * f;
}
const int N = 500001, M = 1000001, inf = 7998244353;
const int dx[] = {1, 2, 2, 1, -1, -2, -2, -1};
const int dy[] = {2, 1, -1, -2, -2, -1, 1, 2};
struct Edge{
    int to, nxt;
    int w;
}e[M];
int tot = 1, head[N];
inline void add_edge(int u, int v, int w){
    tot++;
    e[tot].to = v;
    e[tot].nxt = head[u];
    e[tot].w = w;
    head[u] = tot;
    return;
}
inline void add(int u, int v, int w){
    //printf("add(%d,%d)\n", u, v);
    add_edge(u, v, w);
    add_edge(v, u, 0);
    return;
}
int n, s, t, dis[N], cur[N];
inline bool bfs(){
    for(int i = 1; i <= n; i++) dis[i] = inf;
    queue<int> q; q.push(s);
    cur[s] = head[s], dis[s] = 0;
    while(!q.empty()){
        int u = q.front(); q.pop();
        for(int i = head[u]; i; i = e[i].nxt){
            int v = e[i].to;
            //cout << u << " " << v << " " << q.size() << endl;
            if(dis[v] == inf && e[i].w){
                cur[v] = head[v], dis[v] = dis[u] + 1;
                q.push(v);
                if(v == t) return true;
            }
        }
    }
    return false;
}
inline int dfs(int u, int sum){
    if(u == t) return sum;
    int res = 0;
    for(int i = cur[u]; i; i = e[i].nxt){
        int v = e[i].to;
        cur[u] = i;
        if(dis[v] == dis[u] + 1 && e[i].w){
            int k = dfs(v, min(sum, e[i].w));
            e[i].w -= k, e[i^1].w += k;
            res += k, sum -= k;
        }
    }
    return res;
}
inline int Dinic(){
    int ans = 0;
    while(bfs()){
        ans += dfs(s, inf);
    }
    return ans;
}
bool ban[201][201];
signed main(){
    int nn = read(), m = read();
    int mm = m;
    while(m--){
        int u = read(), v = read();
        ban[u][v] = true;
    }
    n = nn * nn + 2;
    s = nn * nn + 1;
    t = s + 1;
    for(int i = 1; i <= nn; i++){
        for(int j = 1; j <= nn; j++){
            if((i+j) & 1){
                add(s, pos(i, j), 1);
                if(!ban[i][j]){
                    for(int k = 0; k < 8; k++){
                        int xx = i + dx[k], yy = j + dy[k];
                        if(xx >= 1 && xx <= nn && yy >= 1 && yy <= nn){
                            //if(!ban[xx][yy]){
                                add(pos(i, j), pos(xx, yy), inf);
                            //}
                        }
                    }
                }
            }else{
                if(!ban[i][j]){
                    add(pos(i, j), t, 1);
                }
            }
        }
    }
    cout << nn * nn - mm - Dinic() << endl;
    return 0;
}