我拿 ARC111B 做了一下 Dinic 运行速度的测试（尽管这题正解不是网络流）。建图是二分图。

下面两份代码几乎一致，不同的地方打了注释。一个可以 AC，一个 TLE 了 15 个点。

AC 代码：

#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include <bits/stdc++.h>
using namespace std;
const int N = 200005*6;
const int I = INT_MAX;
int h[N], cur[N];
int ds[N];
int S, T, n;
int cnt = 1;
struct edge
{
    int n, t, v;
} e[N << 1];
queue<int> q;
void add(int x, int y, int v)
{
    e[++cnt].n = h[x];
    e[cnt].t = y;
    e[cnt].v = v;
    h[x] = cnt;
    e[++cnt].n = h[y];
    e[cnt].t = x;
    e[cnt].v = 0;
    h[y] = cnt;
    return;
}
inline bool bfs()
{
    memset(ds, -1, sizeof(ds));
    while (!q.empty())
        q.pop();
    ds[S] = 0;
    cur[S] = h[S];//不同
    q.push(S);
    while (!q.empty())
    {
        int p = q.front();
        q.pop();
        for (int i = h[p]; i; i = e[i].n)
        {
            int t = e[i].t, v = e[i].v;
            if (v && ds[t] == -1)
            {
                cur[t] = h[t];//不同
                ds[t] = ds[p] + 1;
                if (t == T)
                    return true;
                q.push(t);
            }
        }
    }
    return false;
}
int dfs(int p = S, int flow = I)
{
    if (p == T)
        return flow;
    if(!flow) return 0;
    int rest = flow;
    for (int i = cur[p]; i && rest; i = e[i].n)
    {
        cur[p] = i;
        int t = e[i].t, v = e[i].v;
        if (v && ds[t] == ds[p] + 1)
        {
            int c = dfs(t, min(rest, int(v)));
            if (!c)
            {
                ds[t] = -1;
            }
            e[i].v -= c;
            e[i ^ 1].v += c;
            rest -= c;
        }
    }
    return flow - rest;
}
inline int dinic()
{
    int res = 0;
    while (bfs())
        res += dfs();
    return res;
}
int a[N], b[N];
int mxcol;
signed main()
{
    // freopen("test3.in", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i] >> b[i];
        mxcol = max(mxcol, max(a[i], b[i]));
    }
    // cout << mxcol << '\n';
    for (int i = 1; i <= n; ++i)
    {
        add(a[i], mxcol + i, 1);
        add(b[i], mxcol + i, 1);
    }
    S = 0;
    T = mxcol + n + 1;
    for (int i = 1; i <= mxcol; ++i)
    {
        add(S, i, 1);
    }
    for (int i = 1; i <= n; ++i)
    {
        add(i + mxcol, T, 1);
    }
    // puts("suc");
    cout << dinic();
    return 0;
}

AC 记录

TLE x 15 代码：

#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#include <bits/stdc++.h>
using namespace std;
const int N = 200005*6;
const int I = INT_MAX;
int h[N], cur[N];
int ds[N];
int S, T, n;
int cnt = 1;
struct edge
{
    int n, t, v;
} e[N << 1];
queue<int> q;
void add(int x, int y, int v)
{
    e[++cnt].n = h[x];
    e[cnt].t = y;
    e[cnt].v = v;
    h[x] = cnt;
    e[++cnt].n = h[y];
    e[cnt].t = x;
    e[cnt].v = 0;
    h[y] = cnt;
    return;
}
inline bool bfs()
{
    memset(ds, -1, sizeof(ds));
    while (!q.empty())
        q.pop();
    ds[S] = 0;
    q.push(S);
    while (!q.empty())
    {
        int p = q.front();
        cur[p] = h[p];//不同
        q.pop();
        for (int i = h[p]; i; i = e[i].n)
        {
            int t = e[i].t, v = e[i].v;
            if (v && ds[t] == -1)
            {
                ds[t] = ds[p] + 1;
                if (t == T)
                    return true;
                q.push(t);
            }
        }
    }
    return false;
}
int dfs(int p = S, int flow = I)
{
    if (p == T)
        return flow;
    if(!flow) return 0;
    int rest = flow;
    for (int i = cur[p]; i && rest; i = e[i].n)
    {
        cur[p] = i;
        int t = e[i].t, v = e[i].v;
        if (v && ds[t] == ds[p] + 1)
        {
            int c = dfs(t, min(rest, int(v)));
            if (!c)
            {
                ds[t] = -1;
            }
            e[i].v -= c;
            e[i ^ 1].v += c;
            rest -= c;
        }
    }
    return flow - rest;
}
inline int dinic()
{
    int res = 0;
    while (bfs())
        res += dfs();
    return res;
}
int a[N], b[N];
int mxcol;
signed main()
{
    // freopen("test3.in", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i] >> b[i];
        mxcol = max(mxcol, max(a[i], b[i]));
    }
    // cout << mxcol << '\n';
    for (int i = 1; i <= n; ++i)
    {
        add(a[i], mxcol + i, 1);
        add(b[i], mxcol + i, 1);
    }
    S = 0;
    T = mxcol + n + 1;
    for (int i = 1; i <= mxcol; ++i)
    {
        add(S, i, 1);
    }
    for (int i = 1; i <= n; ++i)
    {
        add(i + mxcol, T, 1);
    }
    // puts("suc");
    cout << dinic();
    return 0;
}

TLE x 15 记录

求助，这是什么原因啊？