8.29T3 嘉心糖（很稠密的二分图匹配、最大团、偏序传递闭包、最长反链、最小链覆盖、拆点二分图匹配、网络流、模拟网络流）

本文搬运自本人高中时期CSDN博客，若图片加载不出来，可到原文查看：https://blog.csdn.net/zhangtingxiqwq/article/details/141686202

http://cplusoj.com/d/senior/p/NODSX2303C

我以前写的半篇题解： https://blog.csdn.net/zhangtingxiqwq/article/details/135612739

我们现在要求一个 nn 个点 mm 条边的图的最大团，等价于求补图的最大独立集。

由于补图满足偏序关系，等价于求它的最长反链，也就是最小链覆盖。直接拆点二分图，可以获得65分。

考虑这个满足偏序关系的二分图只有 mm 条边不存在，非常稠密，因此我们可以模拟二分图匹配。

首先对于每个点补图中不存在的出边（也就是原图中的边）排序。

我们从后往前贪心找能匹配的最大值， 这部分可以用并查集+双指针搞定。

然后此时我们跑出来的答案和最终答案相差不超过 m\sqrt m ，而最终答案也最多有 m\sqrt m 个未匹配，因此此时我们左部为匹配的点的个数是 m\sqrt m 级别的。

我们考虑模拟匈牙利算法的过程，只不过我们把dfs换成bfs，队列维护左部点。我们现在就是要快速在右部点中找出未vis，且当前点存在出边的点。

而这个东西我们直接对右边为visit的点暴力维护即可。因此如果我们visit成功，那么未visit的点个数-1，如果visit失败，说明我们肯定通过了原图上的一条边（也就是补图上不存在的边）。而原图只有 m\sqrt m 条边。所以单次bfs的过程复杂度是 n+mn+m 的

总复杂度 O(m(n+m))O(\sqrt m(n+m)) ，不能带log

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
#include<bits/stdc++.h>
using namespace std;
#ifdef LOCALd
 #define debug(...) fprintf(stdout, ##__VA_ARGS__)
 #define debag(...) fprintf(stderr, ##__VA_ARGS__)
#else
 #define debug(...) void(0)
 #define debag(...) void(0)
#endif
//#define int long long
inline int read(){int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+
(x<<3)+(ch^48);ch=getchar();}return x*f;}
#define Z(x) (x)*(x)
#define pb push_back
#define fi first
#define se second
//#define M
//#define mo
#define N 200010
int n, m, i, j, k, T;
int shu[N], Go[N], a[N], vis[N], u, v, w, ans; 
vector<int>G[N]; 
map<pair<int, int>, int>mp; 
queue<int> q; 
stack<int>z, Z; 

struct Un_set {
	int i, f[N]; 
	void reset() {
		for(i = 1; i <= n; ++i) f[i] = i; 
	}
	void set(int x) { f[x] = x - 1; }
	int find(int x) {
		if(f[x] == x) return x; 
		return f[x] = find(f[x]); 
	}
}St;

signed main()
{
	#ifdef LOCALd
	  freopen("in.txt", "r", stdin);
	  freopen("out.txt", "w", stdout);
	#endif
//	srand(time(NULL));
//	T=read();
//	while(T--) {
//
//	}
	n = read(); m = read(); 
	for(i = 1; i <= n; ++i) a[i] = i, G[i].pb(i), G[i].pb(0); 
	for(i = 1; i <= m; ++i) {
		k = read(); swap(a[k], a[k + 1]); 
		if(mp[{a[k], a[k + 1]}] || mp[{a[k + 1], a[k]}]) continue; 
		mp[{a[k], a[k + 1]}] = mp[{a[k + 1], a[k]}] = 1; 
		debug("%d %d\n", min(a[k], a[k + 1]), max(a[k], a[k + 1])); 
		G[min(a[k], a[k + 1])].pb(max(a[k], a[k + 1])); 
	}
	for(i = 1; i <= n; ++i) sort(G[i].begin(), G[i].end()); 
	St.reset(); 
	for(i = n; i >= 1; --i) {
		j = n; j = St.find(j); k = G[i].size() - 1; 
		while(j > i) {
			while(G[i][k] > j) --k; 
			if(G[i][k] != j) break; 
			j = St.find(j - 1); 
		}
		if(j > i) Go[i] = j, shu[j] = i, St.set(j); 
		debug("Go[%d] = %d\n", i, Go[i]); 
	}
//	for(i = 1; i <= n; ++i) debug("%lld ", Go[i]); debug("\n"); 
	for(i = 1; i <= n; ++i) if(!Go[i]) {
		for(j = 1; j <= n; ++j) z.push(j), vis[j] = 0; 
		while(!q.empty()) q.pop(); 
		q.push(i); vis[i] = 1; 
		while(!q.empty()) {
			u = q.front(); q.pop(); k = G[u].size() - 1; v = 0; 
			while(!z.empty() && z.top() > u) {
				v = z.top(); z.pop(); 
				while(G[u][k] > v) 
					/*debug("co(%d %d) ", G[u][k], v), */--k; 
				if(G[u][k] != v) {
					debug("%d %d\n", G[u][k], v); 
					if(shu[v]) {
						if(!vis[shu[v]]) q.push(shu[v]); 
						v = 0; 
					}
					else break; 
					continue; 
				}
				Z.push(v); v = 0; 
			}
			while(!Z.empty()) z.push(Z.top()), Z.pop(); 
			if(v) break; 
		}
		while(u && v) {
			debug("[%d]Change(%d %d)\n", i, u, v); 
			shu[v] = v; w = Go[u]; Go[u] = v; 
			v = w; u = shu[v]; 
		}
		if(v) {
			Go[i] = v, shu[v] = i; 
			debug("Let %d to %d\n", i, v); 
		}
	}
	for(i = 1, ans = n; i <= n; ++i) if(Go[i]) --ans; 
	printf("%d", ans); 
	return 0;
}