滴滴编程笔试

const int N = 2000;
const int inf = 1e9;
int bol, n, m, st = N - 2, ed = N - 1;
int head[N], lv[N], vis[N][N], flag[N][N];
struct node {
    int e, flow, nex;
    node() {}
    node(int e, int flow, int nex) : e(e), flow(flow), nex(nex) {}
} edg[N << 3];
inline void add(int s, int e, int flow) {
    edg[bol] = node(e, flow, head[s]);
    head[s] = bol++;
    edg[bol] = node(s, 0, head[e]);
    head[e] = bol++;
}
bool BFS() {
    memset(lv, 0, sizeof lv);
    lv[st] = 1;
    queue<int>q;
    q.push(st);
    while(!q.empty()) {
        int s = q.front();
        q.pop();
        if(s == ed)return true;
        for(int i = head[s]; ~i; i = edg[i].nex) {
            int e = edg[i].e;
            if(!lv[e] && edg[i].flow)
                lv[e] = lv[s] + 1, q.push(e);
        }
    }
    return false;
}
int dfs(int s, int ff) {
    if(!ff || s == ed) return ff;
    int ans = 0;
    for(int i = head[s]; ~i; i = edg[i].nex) {
        int e = edg[i].e;
        if(lv[e] == lv[s] + 1) {
            int u = dfs(e, min(ff - ans, edg[i].flow));
            ans += u;
            edg[i].flow -= u;
            edg[i ^ 1].flow += u;
            if(ans == ff) return ans;
        }
    }
    if(!ans) lv[s] = 0;
    return ans;
}
int dinic() {
    int ans = 0;
    while(BFS()) ans += dfs(st, inf);
    return ans;
}

int main () {
    memset (head, -1, sizeof head);
    int n, m;
    cin >> n >> m;
    while (m --) {
        int a, b;
        scanf ("%d %d", &a, &b);
        flag[a][b + n] = 1;
    }
    for (int i = 1; i <= n; i++) {
        add (st, i, 1);
        add (i + n, ed, 1);
        for (int j = n + 1; j <= n + n; j++) if (!flag[i][j] && i != j){
            add (i, j, inf);
//            cout << i << ' ' << j << endl;
        }
    }
    cout << dinic () / 2 * 2 << endl;
    return 0;
}