大型补档计划
这题是求必须边，而不是不可行边，因为不可行边 = 必须边 + 死掉了的边（貌似lyd第三版书上还是说的不可行边）先跑最大流。
在跑完以后的残余网络上，对于一条当前匹配的边 ((u, v))，对应流量为 (1)，只有他们有可能是必须边。
考虑断开这条边，能否找到增广路，如果能就是可行边，否则是必须边。
新的增广路的端点一定是 (u, v) 中的一个，否则即有更大的最大流。
接下来分类讨论。
-
若是找到一条 (u, v) 的路径且不包括 t，则可以把增广路上的边全部取反，就得到了一组新的答案。
-
若是一个点 u 找到了它的非匹配点 z, 由于 (w(z, t) = 1, w(t, v) = 0)，所以 ((u, v)) 还是构成一个环，包括 t
如果两点都不满足，必然不成环，所以就用 tarjan 算法缩点以后判断在不在一个强连通分量即可。
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 20005, S = 400005, INF = 1e9;
int n, m, T, s, t, q[N], d[N];
int dfn[N], low[N], dfncnt;
int col[N], cnt = 0, st[N], top;
bool ins[N];
struct E{
int next, v, w;
} e[S];
int head[N], numE = 1;
void inline add(int u, int v, int w) {
e[++numE] = (E) { head[u], v, w };
head[u] = numE;
}
bool bfs() {
memset(d, 0, sizeof d);
int hh = 0, tt = 0;
q[0] = s; d[s] = 1;
while (hh <= tt) {
int u = q[hh++];
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (e[i].w && !d[v]) {
d[v] = d[u] + 1;
q[++tt] = v;
if (v == t) return true;
}
}
}
return false;
}
int dinic(int u, int flow) {
if (u == t) return flow;
int rest = flow;
for (int i = head[u]; i && rest; i = e[i].next) {
int v = e[i].v;
if (e[i].w && d[v] == d[u] + 1) {
int 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;
}
bool tarjan(int u) {
dfn[u] = low[u] = ++dfncnt;
ins[u] = true, st[++top] = u;
for (int i = head[u]; i; i = e[i].next) {
int v = e[i].v;
if (!e[i].w) continue;
if (!dfn[v]) tarjan(v), low[u] = min(low[u], low[v]);
else if (ins[v]) low[u] = min(low[u], dfn[v]);
}
if (dfn[u] == low[u]) {
int v; ++cnt;
do {
v = st[top--];
ins[v] = false;
col[v] = cnt;
} while (v != u);
}
}
int main() {
scanf("%d%d%d", &n, &m, &T);
s = n + m + 1, t = n + m + 2;
for (int i = 1, u, v; i <= T; i++) {
scanf("%d%d", &u, &v);
add(u, v + n, 1); add(v + n, u, 0);
}
for (int i = 1; i <= n; i++) add(s, i, 1), add(i, s, 0);
for (int i = 1; i <= m; i++) add(n + i, t, 1), add(t, n + i, 0);
while (bfs() && dinic(s, INF));
for (int i = 1; i <= t; i++)
if (!dfn[i]) tarjan(i);
int ans = 0;
for (int i = 2; i <= 2 * T; i += 2)
if (e[i].w && col[e[i].v] != col[e[i ^ 1].v]) ans++;
printf("%d
", ans);
if (!ans) puts("");
for (int i = 2; i <= 2 * T; i += 2)
if (e[i].w && col[e[i].v] != col[e[i ^ 1].v]) printf("%d ", i >> 1);
}