P8095 题解

题意：

有 \(n\) 头牛和 \(m\) 种麦片，每种麦片只有一箱，每头牛分别有其最喜欢的和第二喜欢的两种不同的麦片。

需要给所有牛制定一个取麦片的先后顺序，使得没有拿麦片的牛的数量最少。

一头牛取麦片的方式是：如果其最喜欢的麦片还在，就直接拿一箱其最喜欢的，

否则，如果其第二喜欢的还在，就拿一箱其第二喜欢的，否则就一箱也不拿。

输出这个顺序对应的排列和没有拿到麦片的牛数的最小值。

\(n,m\le10^5\)。

做法：

设没有拿麦片的牛的数量的最小值为 \(val\)。

则我们将每头牛和其喜欢的麦片连边，设这张二分图的最大匹配数为 \(mch\)，

则我们一定有 \(mch\ge n-val\)，

原因是，所有牛所拥有麦片的种类的 \(n\) 元组，与图中所有符合的二分图匹配是一一对应的。

当然，也许有可能出现 \(mch>n-val\)，

出现这件事的条件是，最大匹配对应的那个麦片种类 \(n\) 元组，无法通过题意中的取法构造出来。

那这时我们猜测，任何一种牛群拿麦片的方式都可以被构造出来。

也就是说，我们要证明的是，对任何一种匹配 \(X\)，都能构造出一个排列，使得：

牛群按照这个排列的顺序取麦片，最后所有牛所拥有麦片种类的 \(n\) 元组就对应了匹配 \(X\)。

如果这个猜测成立，那么最后答案就是最大匹配，那我们考虑能否证明这个猜测。

因为最后要求输出排列，故考虑给出构造性证明。

考虑构造的困难之处，在于匹配与题意中吃草顺序的不匹配，

即某头牛在匹配中应该拿走其第二喜欢的麦片，然而实际上，

它可能因为其最喜欢的麦片还在，从而直接拿走其最喜欢的麦片，

甚至，其最喜欢的麦片有可能是另外一头牛在最终匹配方案中所拥有的麦片，

我们要做的事，是尽量地消除这些错位带来的影响。

我们记最终匹配方案中，第 \(i\) 头牛拿了第 \(t_i\) 种麦片，其最喜欢第 \(f_i\) 种麦片，第二喜欢第 \(s_i\) 种麦片，

当然，在这里我们不需要考虑没拿麦片的牛，因为我们在排列的最后让这些牛尝试取一次麦片即可。

这里有一个性质，即所有 \(t_i\) 互不相同。

我们维护一个当前排列，代表所有已经尝试取过麦片的牛。

首先，我们把所有编号 \(i\) 满足 \(f_i=t_i\) 的牛加入排列末尾，这样显然一定足够优，

而剩下还需要考虑的牛的编号 \(i\)，都满足 \(s_i=t_i\)，设集合 \(S\) 包含了所有编号满足 \(s_i=t_i\) 的牛。

那么，接下来我们会做若干次操作，直到 \(S\) 变成空集。

在每次操作中，我们从 \(S\) 中随便取出一头牛并开始检查，设最初取出的牛编号为 \(u\)，则：

如果此时第 \(f_u\) 种麦片已经不存在了，就直接终止检查；

否则，如果 \(S\) 中不存在牛 \(v\) 满足 \(s_v=f_u\)，我们也直接终止检查；

否则，此时 \(S\) 中一定存在牛 \(v\) 满足 \(s_v=f_u\)，我们将 \((u,v)\) 连边，再对 \(v\) 进行上面的检查。

注意，此处的连边与上面牛与麦片连的边无关，只是用来方便叙述的，

也就是说，每次操作中连的边是在一张独立的新图上的，跟其他次操作以及最初的图无关。

那么，我们在这次操作中检查过的所有牛，一定会形成形如一个环接上一条链的样式，

当然，环长和链长可以是 \(0\)，即可以是纯的一个环或一条链。

考虑此时，我们将所有牛按检查牛顺序的倒序加入排列末尾，并从 \(S\) 中删去这些牛，是足够优的。

为什么？因为，如果让牛们按上面这种构造方式里的顺序来尝试取麦片的话，

所有环上的牛都会拿走它们最喜欢的麦片，而所有链上的牛都会拿走它们第二喜欢的麦片。

具体证明就不赘述了，相信这个也不难，画个图手动模拟一下就能理解。

当然，在排列的最后，我们还需要加入所有在匹配中没有拿到麦片的牛。

这样，我们就对任意一个没有特殊性质的匹配 \(X\)，给出了一种排列顺序，满足：

所有牛按这个顺序去麦片，最后每头牛所拥有的麦片就和 \(X\) 对应。

那么，我们对初始图的最大匹配构造出这样的一个排列顺序即可。

最后一个问题，是如何求二分图的最大匹配，因为本题数据较大，故可以使用网络流，

时间复杂度是 \(O((n+m)\sqrt{n+m})\)，瓶颈在 dinic 算法跑二分图匹配。

因为构造排列的具体实现可能还有一些细节，故给出代码以便参考，当然最好还是自己写。

code：

#include <bits/stdc++.h>

#define fi first
#define se second
#define vi vector
#define mp make_pair
#define pb push_back
#define LL long long
#define pii pair < int , int >
#define SZ(x) ((int)(x.size()))
#define ckmax(a, b) ((a) = max((a), (b)))
#define ckmin(a, b) ((a) = min((a), (b)))
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define edg(i, v, u) for (int i = head[u], v = e[i].to; i; i = e[i].nxt, v = e[i].to)

using namespace std;
inline int read() {
	// 快读
}
const int N (3e5 + 10);
const int INF (2e9 + 10);
struct Edge {
	int fr, to, cp, fl;
};

struct Dinic {
	int n, m;
	int s, t;
	int d[N];
	int cur[N];
	int vis[N];
	vector < Edge > E;
	vector < int > G[N];
	
	void init (int n) {
		E.clear();
		rep (i, 0, n - 1) G[i].clear();
	}
	void adde (int u, int v, int c) {
		E.pb ((Edge) {u, v, c, 0});
		E.pb ((Edge) {v, u, 0, 0});
		int sz = E.size();
		G[u].pb (sz - 2), G[v].pb (sz - 1);
	}
	bool bfs() {
		queue < int > q;
		memset (vis, 0, sizeof (vis));
		q.push (s), d[s] = 0, vis[s] = 1;
		while (!q.empty()) {
			int u = q.front(); q.pop();
			rep (i, 0, SZ (G[u]) - 1) {
				Edge& e = E[G[u][i]];
				if (!vis[e.to] && e.cp > e.fl) 
				  d[e.to] = d[u] + (vis[e.to] = 1), q.push (e.to);
			}
		}
		return vis[t];
	}
	int dfs (int u, int flw) {
		if (u == t || !flw) return flw;
		int flow = 0;
		for (int& i = cur[u]; i < SZ (G[u]); i++) {
			Edge& e = E[G[u][i]]; int f = 0;
			if (d[e.to] == d[u] + 1 && (f = dfs (e.to, min (flw, e.cp - e.fl))) > 0) {
				e.fl += f, E[G[u][i] ^ 1].fl -= f, flow += f, flw -= f;
				if (flw == 0) break;
			}
		}
		if (flow == 0) d[u] = 0;
		return flow;
	}
	int mxflow (int s, int t) {
		this -> s = s, this -> t = t;
		int flow = 0;
		while (bfs()) {
			memset (cur, 0, sizeof (cur));
			flow += dfs (s, INF);
		}
		return flow;
	}
} Dinic;

int tot;
int num;
int n, m;
int s, t;
int a[N];
int b[N];
int rb[N];
int res[N];
int buk[N];
int ned[N];

int main() {
	n = read(), m = read();
	memset (rb, -1, sizeof rb);
	rep (i, 1, n) a[i] = read() + n, b[i] = read() + n;
	s = n + m + 1, t = s + 1;
	rep (i, 1, n) {
		Dinic.adde (s, i, 1);
		Dinic.adde (i, a[i], 1);
		Dinic.adde (i, b[i], 1);
	}
	rep (i, 1, m) Dinic.adde (i + n, t, 1);
	int val = n - Dinic.mxflow (s, t);
	printf ("%d\n", val);
	rep (u, 1, n) for (int id : Dinic.G[u]) {
		Edge e = Dinic.E[id];
		if (e.fl != 1 || e.cp == 0) continue;
		if (e.to == a[u]) {
			res[++tot] = u, buk[a[u]] = 1, ned[u] = 1; break;
		}
		rb[b[u]] = u, ned[u] = 2;
	}
	rep (i, 1, n) {
		if (ned[i] != 2) continue;
		int u = i;
		stack < int > stk;
		while (true) {
			if (ned[u] == 1) break;
			stk.push (u);
			if (buk[a[u]] || rb[a[u]] == -1 || rb[a[u]] == i) break;
			ned[u] = 1, u = rb[a[u]];
		}
		while (!stk.empty()) {
			u = stk.top();
			ned[u] = 1;
			if (!buk[a[u]]) buk[a[u]] = 1;
			else buk[b[u]] = 1;
			res[++tot] = u, stk.pop();
		}
	}
	rep (i, 1, n) if (ned[i] != 1) res[++tot] = i;
	rep (i, 1, tot) printf ("%d\n", res[i]);
	return 0;
}