CH#17C 舞动的夜晚

原题链接

即求二分图的不可行边数量，因为不保证是完备匹配，所以需要通过网络流求出任意一组最大匹配，并建立新图判断。

建新图：对于跑完网络流的图上已经匹配的边，建立反边；对于没有匹配的边，建立正边（图只改变边的方向，别的结构不变）。

有结论：

必须边的判定条件为：\((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\n", s);

	if (!s)

	{

		printf("\n");

		return 0;

	}

	for (i = 1; i < s; i++)

		printf("%d ", an[i]);

	printf("%d", an[s]);

	return 0;

}

巴特西

CH#17C 舞动的夜晚

原题链接

最新文章

热门文章