AcWing 380 舞动的舞会

#include <bits/stdc++.h>
using namespace std;
#define lc k << 1
#define rc k << 1 | 1
#define lcon lc, l, mid
#define rcon rc, mid + 1, r
#define Mid int mid = ((l + r) >> 1)
#define Init int k, int l, int r
#define mp(a, b) make_pair(a, b)
#define pii pair<int, int>
#define lb(x) (x & (-x))
#define FR for (int i = head[u], v = e[i].to; i; i = e[i].next, v = e[i].to)
#define For(i, a, b) for (int i = a; i <= b; i++)
#define Tor(i, a, b) for (int i = a; i >= b; i--)
#define ll long long
#define gc() getchar()
template <class T>
inline void read(T &x)
{
    T flag = 1;
    x = 0;
    char ch = gc();
    for (; !isdigit(ch); ch = gc())
        if (ch == '-')
            flag = -1;
    for (; isdigit(ch); ch = gc())
        x = (x << 1) + (x << 3) + (ch & 15);
    x *= flag;
    return;
}
template <typename T, typename... Args>
inline void read(T &t, Args &...args)
{
    read(t);
    read(args...);
}
template <class T>
inline void write(T x)
{
    if (x < 0)
        putchar('-'), x = -x;
    T y = 1;
    int len = 1;
    for (; y <= x / 10; y *= 10)
        ++len;
    for (; len; --len, x %= y, y /= 10)
        putchar(x / y + 48);
}
#define _ (int)(1e5 + 5)
struct edge
{
    int next, to, w;
} e[_ << 1];
int cnt = 1, head[_];
void add(int f, int t, int v)
{
    e[++cnt] = edge{head[f], t, v};
    head[f] = cnt;
}
int n, m, T, tim, s, t;
int d[_], now[_];
int BFS()
{
    memset(d, 0, sizeof d);
    d[s] = 1, now[s] = head[s];
    queue<int> Q;
    Q.push(s);
    while (!Q.empty())
    {
        int u = Q.front();
        Q.pop();
        FR
        {
            if (!e[i].w || d[v])
                continue;
            Q.push(v);
            now[v] = head[v];
            d[v] = d[u] + 1;
            if (v == t)
                return 1;
        }
    }
    return 0;
}
int Dinic(int u, int flow)
{
    if (u == t || !flow)
        return flow;
    int rest = flow, k;
    for (int i = now[u], v = e[i].to; i && rest; i = e[i].next, v = e[i].to)
    {
        now[u] = i;
        if (!e[i].w || d[v] != d[u] + 1)
            continue;
        k = Dinic(v, min(rest, e[i].w));
        if (!k)
            d[v] = 0;
        e[i].w -= k;
        e[i ^ 1].w += k;
        rest -= k;
    }
    return flow - rest;
}
int cot, top;
pii load[_];
map<pii, int> IsMatched;
int dfn[_], low[_], st[_], c[_];
void tarjan(int u)
{
    dfn[u] = low[u] = ++tim;
    st[++top] = u;
    FR if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
    else if (!c[v]) low[u] = min(low[u], dfn[v]);
    if (dfn[u] == low[u])
    {
        ++cot;
        int v;
        do
            v = st[top--], c[v] = cot;
        while (v != u);
    }
}
int main()
{
    read(n, m, T);
    s = n + m + 1, t = n + m + 2; // 超级源点
    For(i, 1, n) add(s, i, 1), add(i, s, 0);
    For(i, n + 1, m + n) add(i, t, 1), add(t, i, 0);
    For(i, 1, T)
    {
        int u, v;
        read(u, v);
        add(u, v + n, 1);
        add(v + n, u, 0);
        load[i] = mp(u, v); //  存边
    }
    while (BFS())
        while (Dinic(s, 0x3f3f3f3f))
            ;
    for (int i = 2; i <= cnt; i += 2)
        if (e[i ^ 1].w)
            IsMatched[mp(e[i ^ 1].to, e[i].to)] = 1; // 判断边是否有流量

    For(i, 1, cnt) e[i].next = e[i].to = e[i].w = 0;
    cnt = 1;
    memset(head, 0, sizeof head); // 清空

    For(i, 1, T)
    {
        int u, v;
        u = load[i].first, v = load[i].second + n;
        if (IsMatched[mp(u, v)])
            add(v, u, 0);
        else
            add(u, v, 0); // 重新建边
    }

    For(i, 1, n + m) if (!dfn[i]) tarjan(i);

    int ans = 0;
    For(i, 1, T)
    {
        int u, v;
        u = load[i].first, v = load[i].second + n;
        if (!IsMatched[mp(u, v)] && c[u] != c[v]) // 无流量且不在同一强连通分量
            ans++;
    }
    write(ans), putchar(10);
    For(i, 1, T)
    {
        int u, v;
        u = load[i].first, v = load[i].second + n;
        if (!IsMatched[mp(u, v)] && c[u] != c[v])
            write(i), putchar(32);
    }
    return 0;
}

写挂了 ， 但是不知道有什么问题