原题链接
即求二分图的不可行边数量，因为不保证是完备匹配，所以需要通过网络流求出任意一组最大匹配，并建立新图判断。
建新图：对于跑完网络流的图上已经匹配的边，建立反边；对于没有匹配的边，建立正边（图只改变边的方向，别的结构不变）。
有结论：
- 必须边的判定条件为：((x,y))的流量为(1)，并且在残量网络上属于不同的强联通分量。
- 可行边的判定条件为：((x,y))的流量为(1)，或者在残量网络上属于同一个强联通分量。
所以我们在新图上跑(tarjan)，再逐边检验即可。
#include<cstdio>
#include<cstring>
using namespace std;
const int N = 2e4 + 10;
const int M = 2e5 + 10;
struct dd {
int x, y;
};
dd a[M];
int fi[N], di[M << 1], ne[M << 1], da[M << 1], cfi[N], cdi[M], cne[M], dfn[N], low[N], sta[N], bl[N], cu[N], de[N], q[M << 1], an[M], l = 1, tp, lc, SCC, st, ed, ti;
bool v[N];
inline int re()
{
int x = 0;
char c = getchar();
bool p = 0;
for (; c < '0' || c > '9'; c = getchar())
p |= c == '-';
for (; c >= '0' && c <= '9'; c = getchar())
x = x * 10 + c - '0';
return p ? -x : x;
}
inline void add(int x, int y, int z)
{
di[++l] = y;
da[l] = z;
ne[l] = fi[x];
fi[x] = l;
}
inline void add_c(int x, int y)
{
cdi[++lc] = y;
cne[lc] = cfi[x];
cfi[x] = lc;
}
inline int minn(int x, int y)
{
return x < y ? x : y;
}
bool bfs()
{
int i, x, y, head = 0, tail = 1;
memset(de, 0, sizeof(de));
q[1] = st;
de[st] = 1;
while (head ^ tail)
{
x = q[++head];
for (i = fi[x]; i; i = ne[i])
if (!de[y = di[i]] && da[i] > 0)
{
de[y] = de[x] + 1;
if (!(y ^ ed))
return true;
q[++tail] = y;
}
}
return false;
}
int dfs(int x, int k)
{
int y, mi;
if (!(x ^ ed))
return k;
for (int &i = cu[x]; i; i = ne[i])
if (!(de[y = di[i]] ^ (de[x] + 1)) && da[i] > 0)
{
mi = dfs(y, minn(k, da[i]));
if (mi > 0)
{
da[i] -= mi;
da[i ^ 1] += mi;
return mi;
}
}
return 0;
}
void tarjan(int x)
{
int i, y;
dfn[x] = low[x] = ++ti;
sta[++tp] = x;
v[x] = 1;
for (i = cfi[x]; i; i = cne[i])
{
if (!dfn[y = cdi[i]])
{
tarjan(y);
low[x] = minn(low[x], low[y]);
}
else
if (v[y])
low[x] = minn(low[x], dfn[y]);
}
if (!(dfn[x] ^ low[x]))
{
SCC++;
do
{
y = sta[tp--];
bl[y] = SCC;
v[y] = 0;
} while (x ^ y);
}
}
int main()
{
int i, n, m, k, x, y, s = 0;
n = re();
m = re();
k = re();
st = n + m + 1;
ed = st + 1;
for (i = 1; i <= k; i++)
{
x = re();
y = re() + n;
a[i].x = x;
a[i].y = y;
add(x, y, 1);
add(y, x, 0);
}
for (i = 1; i <= n; i++)
{
add(st, i, 1);
add(i, st, 0);
}
for (i = 1; i <= m; i++)
{
add(i + n, ed, 1);
add(ed, i + n, 0);
}
while (bfs())
{
for (i = 1; i <= ed; i++)
cu[i] = fi[i];
while (dfs(st, 1e9) > 0);
}
for (i = 2; i <= l; i++)
if (da[i])
add_c(di[i ^ 1], di[i]);
for (i = 1; i <= ed; i++)
if (!dfn[i])
tarjan(i);
for (i = 1; i <= k;i++)
if (bl[a[i].x] ^ bl[a[i].y] && da[i << 1])
an[++s] = i;
printf("%d
", s);
if (!s)
{
printf("
");
return 0;
}
for (i = 1; i < s; i++)
printf("%d ", an[i]);
printf("%d", an[s]);
return 0;
}