萌新刚学 OI，Dinic TLE 3 个点求助/kk

#include <cstdio>
#include <queue>
#include <cstring>
#define MAXN 2000
#define INF 0x7f7f7f7f
#define QWQ cout << "QWQ" << endl;
using namespace std;
int min(int x, int y) {return ((x < y) ? (x) : (y));}
struct node {
    int id, val;
    int next;
} gra[MAXN * MAXN * 2 + 10];
int n, m, s, t;
int tot = 1, head[MAXN * MAXN + 10], dis[MAXN * MAXN + 10], Now[MAXN * MAXN + 10];
int dx[5] = {0, 0, 0, 1, -1};
int dy[5] = {0, 1, -1, 0, 0};
int ddx[9] = {0, 1, -1, 2, -2, 1, -1, 2, -2};
int ddy[9] = {0, 2, -2, 1, -1, -2, 2, -1, 1};
void link(int x, int y, int z) {
    gra[++tot].id = y, gra[tot].val = z, gra[tot].next = head[x], head[x] = tot;
    gra[++tot].id = x, gra[tot].val = 0, gra[tot].next = head[y], head[y] = tot;
}
bool vis[MAXN + 10][MAXN + 10];
bool check(int x, int y) {return ((x >= 1 && x <= n && y >= 1 && y <= n) && !vis[x][y]);}
int get(int x, int y) {return ((x - 1) * n + y);}
void connect() {
    for(int p = 1; p <= n; p++) {
        for(int i = 1; i <= n; i++) {
            if(vis[p][i]) continue;
            if((p + i) % 2 == 1) link(s, get(p, i), 1);
            else link(get(p, i), t, 1);
        }
    }
    for(int p = 1; p <= n; p++) {
        for(int i = 1; i <= n; i++) {
            if((p + i) % 2 == 0 || vis[p][i]) continue;
            for(int j = 1; j <= 8; j++) {
                int xx = p + ddx[j], yy = i + ddy[j];
                if(check(xx, yy))
                    link(get(p, i), get(xx, yy), INF);
            }
        }
    }
}
bool bfs() {
    memset(dis, 0, sizeof(dis));
    queue <int> que;
    que.push(s), dis[s] = 1, Now[s] = head[s];
    while(!que.empty()) {
        int fr = que.front(); que.pop();
        for(int p = head[fr]; p; p = gra[p].next) {
            int v = gra[p].id, w = gra[p].val;
            if(w && !dis[v]) {
                que.push(v);
                Now[v] = head[v];
                dis[v] = dis[fr] + 1;
                if(v == t) return 1;
            }
        }
    }
    return 0;
}
int Dinic(int u, int over) {
    if(u == t) return over;
    int res = over;
    for(int p = Now[u]; p; p = gra[p].next) {
        int v = gra[p].id, w = gra[p].val;
        Now[u] = p;
        if(w && dis[v] == dis[u] + 1) {
            int k = Dinic(v, min(res, w));
            if(!k) dis[v] = 0x7f7f7f7f;
            gra[p].val -= k;
            gra[p ^ 1].val += k;
            res -= k;
        }
    }
    return over - res;
}
signed main() {
    scanf("%d%d", &n, &m), s = n * n + 1, t = n * n + 2; 
    for(int p = 1, x, y; p <= m; p++) {
        scanf("%d%d", &x, &y); 
        vis[x][y] = 1;
    }
    connect();
    int maxn = 0, rest = 0;
    while(bfs()) {
        for(int p = 1; p <= n; p++)
            Now[p] = head[p];
        maxn += Dinic(s, 0x7f7f7f7f);
    }
    printf("%d", n * n - m - maxn);
    //cout << maxn << endl;
}

不知道为啥 TLE 了 3 个点，明明加了当前弧优化的，求助/kk