Codeforces 1037E Trips

时间:2022-01-26 20:26:52

原题

题目大意:

有\(n\)个人,起初他们都不是朋友。总共有\(m\)天,每天会有两个人成为朋友。他们计划在晚上出去旅游,对于一个人,有如下两种情况:

1.要么他不出去旅游

2.要么有至少\(k\)个朋友跟他一起出去

其中\(n,m,k\)都会给出

(注意,友谊是非传递性的,比如\(a\)和\(b\)是朋友,\(b\)和\(c\)是朋友,但\(a\)和\(c\)不一定是朋友)

你的任务是,对于\(1\)到\(m\)天,输出每天晚上最多可以出去玩的人数

首先,我们将题目抽象为一张无向图,问题转化为可以动态加边,在某一刻时最多能选多少个点,\(s.t.\)被选的点中任意一点都与其他被选的点有至少\(k\)条连边。

正向不太好做,我们可以逆向考虑:

首先把所有的边都加进来。显然此时度数还小于\(k\)的点是不可能对答案有贡献了,因此要删去,同时更新一下与它相邻的点的度数。重复以上操作,直到所有点的度数都大于等于\(k\)。此时剩余点的数量就是第\(m\)天时的答案。然后我们倒着删边,并重复上述操作,然后记录一下这一天的答案。最后注意一下输出顺序就OK啦!

代码不长:

#include <bits/stdc++.h>

using namespace std;

#define N 200000

int n, m, k, from[N+5], to[N+5], deg[N+5], del[N+5], ans[N+5], cnt; //del是删除标记
set<int> G[N+5]; //存图 void d(int u) { //删除
if(del[u] || deg[u] >= k) return ; //显然要返回嘛
queue<int> q;
q.push(u); //准备开始更新
del[u] = 1;
--cnt; //更新答案
while(!q.empty()) {
int x = q.front(); q.pop();
for(auto v : G[x]) { //请食用c++11
--deg[v]; //因为这个点被删除了,相当于它与相邻点的连边也没了,因此要把相邻点的度数减去1
if(deg[v] < k && !del[v]) {
q.push(v); //准备下一次更新
del[v] = 1;
--cnt; //更新答案
}
}
}
} int main() {
ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> n >> m >> k;
cnt = n;
for(int i = 1, x, y; i <= m; ++i)
cin >> x >> y, from[i] = x, to[i] = y, deg[x]++, deg[y]++, G[x].insert(y), G[y].insert(x);
for(int i = 1; i <= n; ++i) d(i);
ans[m] = cnt; //记录答案
for(int i = m; i >= 1; --i) {
if(!del[from[i]]) --deg[to[i]]; //注意,这里要特判一下,因为若连边的某一端被删除了,那另一端的度数一定已经被减掉1了
if(!del[to[i]]) --deg[from[i]];
G[from[i]].erase(to[i]), G[to[i]].erase(from[i]);
d(from[i]), d(to[i]); //尝试删除
ans[i-1] = cnt; //记录答案
}
for(int i = 1; i <= m; ++i) cout << ans[i] << endl;
return 0;
}