题解 P5361 【[SDOI2019]热闹又尴尬的聚会】
龙之吻—水货
2019-05-08 15:44:09
# [SDOI2019]热闹又尴尬的聚会
## 题目大意
给你一个无向图，求这个图的一个子图，其最小度数为 $p$，再求这个图的一个点独立集，其大小为 $q$，使得 $\lfloor \frac{n}{q+1} \rfloor\le p$ 且 $\lfloor \frac{n}{p+1} \rfloor\le q$。
## 解题报告
看这题的第一眼，就感觉要考虑 $p$ 和 $q$ 的关系，于是打了一个表，发现当 $n = 100$ 的时候，$p, q$ 中任意一个达到 $10$ 左右的时候，另一个就可以取任意值了，所以这题似乎只需要求一个较优解就可以了。
在打同步赛的时候，感觉 $q$ 的最大值似曾相识，于是考虑先求出 $q$ 的最大值，然后找出相应的最小的 $q$，统计答案即可。
但是，众所周知，求一般图的点的最大独立集及其难写，而且时间复杂度也并不对劲。所以在考场上我想了一个比较 naive 的贪心求法，就是把点按度数排序，之后能选则选。
虽然这么求独立集并不清真，但似乎效率还并不差，于是就这么求出了 $q$。
然后，就十分简单了，根据 $q$ 求出最小的 $p$，然后进行一个类似拓扑排序的东西，大体就是如果一个点的度数小于 $p$，就把这个点删去，并计算一下影响。
整个算法的复杂度应该是 $O(T(n\log{n} + m))$ 的，时间复杂度的瓶颈就是边数和 sort，完全可过。
本来以为这个算法能骗 $50$ ~ $60$ 分的，结果交上去，一遍 $AC$ ？！！！
最后，附上想要骗分却直接 AC 的 Code :
```cpp
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
std::vector<int> e[10007];
class Solution{
private :
static const int maxn = 1e4 + 7;
int t, n, m, id[maxn], res[maxn], cnt, need, degree[maxn];
int tot, ans[maxn];
bool vis[maxn], out[maxn];
std::queue<int> q;
void clear() {
for (register int i = 1; i <= n; i++) {
std::vector<int>().swap(e[i]);
}
}
static bool cmp(int x, int y) {
return e[x].size() < e[y].size();
}
void topoSort() {
for (register int i = 1; i <= n; i++) {
if (degree[i] < need) {
q.push(i);
}
}
while (!q.empty()) {
int now = q.front();
q.pop();
out[now] = 1;
for (auto v : e[now]) {
if (degree[v] == need) {
q.push(v);
continue;
}
degree[v]--;
}
}
}
public :
Solution() {
scanf("%d", &t);
while (t--) {
get();
solve();
clear();
}
}
void get() {
scanf("%d %d", &n, &m);
for (register int i = 1, u, v; i <= m; i++) {
scanf("%d %d", &u, &v);
e[u].push_back(v);
e[v].push_back(u);
}
}
void solve() {
for (register int i = 1; i <= n; i++) {
id[i] = i;
degree[i] = e[i].size();
}
memset(vis, 0, sizeof(vis));
std::sort(id + 1, id + 1 + n, cmp);
cnt = tot = 0;
for (register int i = 1; i <= n; i++) {
int now = id[i];
if (!vis[now]) {
vis[now] = 1;
res[++cnt] = now;
for (auto v : e[now]) {
vis[v] = 1;
}
}
}
need = n;
for (register int i = 1; i <= n; i++) {
if (n / (i + 1) <= cnt && n / (cnt + 1) <= i) {
need = i;
break;
}
}
topoSort();
for (register int i = 1; i <= n; i++) {
if (!out[i]) {
ans[++tot] = i;
}
}
printf("%d", tot);
for (register int i = 1; i <= tot; i++) {
printf(" %d", ans[i]);
}
putchar('\n');
//printf("%d\n", need);
printf("%d", cnt);
for (register int i = 1; i <= cnt; i++) {
printf(" %d", res[i]);
}
putchar('\n');
}
};
Solution sol;
int main() {}
```