CF1721F 题解

First Post:

Last Update:

这题考察终态的思想，有启发意义和教育性。

考虑最后删到最大匹配为 的时候是什么状态，此时没有任何一对点之间有边，即图是个独立集。这就提示我们向独立集转化问题。

注意到最大独立集 + 最大匹配在每个时刻都等于总点数，所以一次操作后，点数 ，最大匹配 ，所以最大独立集不变。

所以，只要我们每次都删一个非最大独立集的点，就可以保证最大匹配恰好减少 了 ！

那么匹配边如何维护呢？

设最大独立集为 ，那么 与 之间一定有完美匹配，因为如果有一个 中的点无法匹配，那么其肯定可以被纳入独立集中，与最大性矛盾。所以我们在最初求出 和 中的最大匹配，然后每次删点的 时候就把对应的匹配边删掉即可。

事实上，我们求最大独立集的时候会跑出一个最大匹配，而这个最大匹配恰恰就是 与 之间的最大匹配，因为每条匹配边至少有一个端点不属于 ，而匹配大小等于 

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
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 5,M = 2e6 + 5;
int n1,n2,m,tot,Q;
int fir[N],nxt[M],to[M],w[M],ect = 1;
vector<int> G[N];

inline void addedge(int u1,int v1,int w1)
{
	nxt[++ect] = fir[u1];fir[u1] = ect;to[ect] = v1;w[ect] = w1;
}
inline void ins(int u1,int v1,int w1) { addedge(u1,v1,w1);addedge(v1,u1,0);}
int dep[N],cur[N];
inline bool bfs(int S,int T)
{
	for(int i = 1;i <= tot;i++) dep[i] = 1e9,cur[i] = fir[i];
	queue<int> Q;Q.push(S);dep[S] = 0;
	while(!Q.empty())
	{
		int x = Q.front();Q.pop();
		for(int i = fir[x],y;y = to[i],i;i = nxt[i])
			if(w[i] && dep[y] > dep[x] + 1)
			{
				dep[y] = dep[x] + 1;
				Q.push(y);
			}
	}
	return dep[T] < 1e9;
}
int dfs(int u,int t,int limit)
{
	if(u == t || !limit) return limit;
	int flow = 0,f;
	for(int i = cur[u],v;v = to[i],i;i = nxt[i])
	{
		cur[u] = i;
		if((dep[v] == dep[u] + 1) && w[i] && (f = dfs(v,t,min(limit,w[i]))))
		{
			flow += f;
			limit -= f;
			w[i] -= f;
			w[i ^ 1] += f;
			if(!limit) break;
		}
	}
	return flow;
}
inline int dinic(int S,int T)
{
	int res = 0;
	while(bfs(S,T)) res += dfs(S,T,2e9);
	return res;
}


int vx[N],vy[N];
int ml[N],mr[N]; // 下标是左、右部点
bool inset[N];

void dfs0(int x)
{
	if(vx[x]) return;
	vx[x] = true;
	for(auto y : G[x])
		if(mr[y] && !vy[y] && mr[y] != x)
		{
			vy[y] = true;
			dfs0(mr[y]);
		}
}
void GetSet()
{
	for(int i = 1;i <= n1;i++)
		for(int e = fir[i],v;v = to[e],e;e = nxt[e])
			if(v > n1 && v <= n1 + n2 && w[e] == 0)
				mr[v - n1] = i;
	for(int i = 1;i <= n2;i++)
		ml[mr[i]] = i;
	for(int i = 1;i <= n1;i++)
		if(!ml[i]) dfs0(i);
	for(int i = 1;i <= n1;i++) if(vx[i]) inset[i] = true;
	for(int i = 1;i <= n2;i++) if(!vy[i]) inset[i + n1] = true;
	// printf("inset:");for(int i = 1;i <= n1 + n2;i++) printf("%d ",inset[i]);printf("\n");
}	

int nd[N],cnt;
long long sum[N];
map<pair<int,int>,int> mp;
int main()
{
	cin >> n1 >> n2 >> m >> Q;
	tot = n1 + n2 + 2;
	for(int i = 1;i <= m;i++)
	{
		int u,v;
		cin >> u >> v;
		ins(u,v + n1,1);
		G[u].push_back(v);
		mp[make_pair(u,v)] = i;
	}
	int S = n1 + n2 + 1,T = n1 + n2 + 2;
	for(int i = 1;i <= n1;i++) ins(S,i,1);
	for(int i = 1;i <= n2;i++) ins(i + n1,T,1);
	dinic(S,T);
	GetSet();
	// printf("ml: ");for(int i = 1;i <= n1;i++) printf("%d ",ml[i]);printf("\n");
	// printf("mr: ");for(int i = 1;i <= n2;i++) printf("%d ",mr[i]);printf("\n");
	for(int i = 1;i <= n1 + n2;i++) if(!inset[i]) nd[++cnt] = i;
	for(int i = 1;i <= cnt;i++)
	{
		int u = nd[i],v = u <= n1 ? ml[u] : mr[u - n1];
		assert(v);
		// if(u <= n1) printf("mth:%d-%d\n",u,v);
		// else printf("mth:%d-%d\n",v,u - n1);
		sum[i] = sum[i - 1] + mp[u <= n1 ? make_pair(u,v) : make_pair(v,u - n1)];
	}
	for(int _ = 1;_ <= Q;_++)
	{
		int op;
		cin >> op;
		if(op == 1)
		{
			printf("1\n");
			if(nd[cnt] > n1) printf("%d\n",-(nd[cnt] - n1));
			else printf("%d\n",nd[cnt]);
			printf("%lld\n",sum[--cnt]);
		}
		else
		{
			printf("%d\n",cnt);
			for(int i = 1;i <= cnt;i++) 
			{
				int u = nd[i],v = u <= n1 ? ml[u] : mr[u - n1];
				assert(v);
				printf("%d ",mp[u <= n1 ? make_pair(u,v) : make_pair(v,u - n1)]);
			}
			printf("\n");
		}
		fflush(stdout);
	}
	return 0;
}
≡