P5361 [SDOI2019]热闹的聚会与尴尬的聚会
W00M
·
·
个人记录
[SDOI2019]热闹的聚会与尴尬的聚会
讲真的,
这道题我本来没看懂,
后来看到题解里说是至少 p 的时候我才意识到我读错题了...
既然是至少 p ,
那就简单多了.
我们先仔细看一下题,
我们发现 p 和 q 都是越大越好,
而且是都大最好,
因为两个不等式里的 p 和 q 都是一个在分子而另一个在分母.
那我们就先想一下第一个问题,
如何求一个尽可能大的 p .
通过读题我们发现,
所以我们就可以贪心的每次找点权最小的点,
然后删掉它和它相连的边,
如果删除之后的点权最小的点的点权比当前的最小点权要大,
那么它就是一个更优解.
我们再看第二个问题,
很显然,
是让我们求一个独立集,
但是不一定非得是最大独立集,
所以我们就可以贪心一波,
每次找到点权最小的点,
删除它和与它相连的点,
保留最后的图,
最后剩下的点就是一个近似的最大独立集.
我们发现,
这两个问题的解决过程非常的相似,
都是从点权最小的点开始删除,
一个是删除相连的边,
另一个是删除相连的点,
所以我们就可以把这两个问题写到一个过程里.
然后就有了下面的代码.
code:
```cpp
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int read(){
int x = 0;
char ch = getchar();
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)){
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return x;
}
const int N = 1e4 + 5, M = 2e5 + 5;
int T, n, m;
int tot, to[M], nxt[M], head[N];
int du[N], ans1, ans2, tot1, tot2, sat[N], sun[N];
priority_queue <pair <int, int > > q;
bool flag[N];
void add(int u, int v){
to[++tot] = v, nxt[tot] = head[u], head[u] = tot;
}
void init(){
n = read(), m = read();
while (q.size()) q.pop();
memset(du, 0, sizeof(int) * (n + 1));
memset(head, 0, sizeof(int) * (n + 1));
memset(flag, 0, sizeof(int) * (n + 1));
ans1 = ans2 = tot = tot1 = tot2 = 0;
for (int i = 1; i <= m; i++){
int u = read(), v = read();
add(u, v); add(v, u);
du[u]++, du[v]++;
}
}
void solve(){
for (int i = 1; i <= n; i++) q.push(make_pair(-du[i], i));
while (q.size()){
int x = q.top().second; q.pop();
if (flag[x]) continue;
if (du[x] > ans1 && !tot1){
ans1 = du[x];
for (int i = 1; i <= n; i++){
if (!flag[i]) sat[++tot1] = i;
}
}
sun[++tot2] = x;
flag[x] = 1;
for (int i = head[x]; i; i = nxt[i]){
int y = to[i];
if (flag[y]) continue;
flag[y] = 1;
du[x]--, du[y]--;
}
q.push(make_pair(-du[x], x));
}
}
void print(){
printf("%d ", tot1);
for (int i = 1; i <= tot1; i++) printf("%d ", sat[i]);
printf("\n");
printf("%d ", tot2);
for (int i = 1; i <= tot2; i++) printf("%d ", sun[i]);
printf("\n");
}
int main(){
T = read();
while (T--){
init();
solve();
print();
}
return 0;
}
```
woc!!!
过样例了!
我过样例了兄弟!
80兄弟!
我这乱写的代码居然80!
也没仔细检查一下,
甚至没有严谨证明,
反正本来就是求近似解,
贪心就是了.
然后我看了一下错误信息,
我的正确性是没有问题的,
意思就是我的代码求出的解一定符合这两个问题,
但是它的 $p$ 和 $q$ 不一定符合条件,
所以我就开始想,
如何让 $p$ 或者 $q$ 更大一些...
# 突然!!!
很快啊!!!
很快我就发现了!!!
我这个代码有问题!
```cpp
if (du[x] > ans1 && !tot1){
ans1 = du[x];
for (int i = 1; i <= n; i++){
if (!flag[i]) sat[++tot1] = i;
}
}
```
注意这个if,
有没有发现这个if只能运行一次!
然后我就有了一个大胆的想法...
before:
```cpp
printf("%d ", tot1);
for (int i = 1; i <= tot1; i++) printf("%d ", sat[i]);
```
after:
```cpp
printf("%d ", n);
for (int i = 1; i <= n; i++) printf("%d ", i);
```
哈哈哈草,
笑死我了,
我直接输出 $1 \sim n$ 居然80分哈哈哈哈!
然后我就想了一下,
随机图中的 $p$ 好像不会太小,
$q$ 也是,
但是仍然是80,
我想要在独立集上再下功夫难度比较大,
因为最大独立集是npc问题,
而其他近似解都是诸如模拟退火,二分之类的.
所以我就只能在第一个问题上下功夫.
然后我按照最初的思路重新写了一份代码,
```cpp
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int read(){
int x = 0;
char ch = getchar();
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)){
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return x;
}
const int N = 1e4 + 5, M = 2e5 + 5;
int T, n, m;
int tot, to[M], nxt[M], head[N];
int du[N], num, ans1, ans2, sat[N], sun[N];
priority_queue <pair <int, int > > q;
bool flag[N];
void add(int u, int v){
to[++tot] = v, nxt[tot] = head[u], head[u] = tot;
}
void init(){
n = read(), m = read();
while (q.size()) q.pop();
memset(du, 0, sizeof(int) * (n + 1));
memset(head, 0, sizeof(int) * (n + 1));
memset(flag, 0, sizeof(int) * (n + 1));
num = ans1 = ans2 = tot = 0;
for (int i = 1; i <= m; i++){
int u = read(), v = read();
add(u, v); add(v, u);
du[u]++, du[v]++;
}
}
void solve(){
bool qwq = 1;
for (int i = 1; i <= n; i++) q.push(make_pair(-du[i], i));
while (q.size()){
int x = q.top().second; q.pop();
if (du[x] > num && qwq){
num = du[x];
for (int i = 1; i <= n; i++){
if (!flag[i]) sat[++ans1] = i;
}
}
else qwq = 0;
if (flag[x]) continue;
sun[++ans2] = x;
flag[x] = 1;
for (int i = head[x]; i; i = nxt[i]){
int y = to[i];
if (flag[y]) continue;
flag[y] = 1;
du[x]--, du[y]--;
q.push(make_pair(-du[y], y));
}
}
}
void print(){
printf("%d ", ans1);
for (int i = 1; i <= ans1; i++) printf("%d ", sat[i]);
printf("\n");
printf("%d ", ans2);
for (int i = 1; i <= ans2; i++) printf("%d ", sun[i]);
printf("\n");
}
int main(){
T = read();
while (T--){
init();
solve();
print();
}
return 0;
}
```
# 草,
爆零了,
# 淦!
然后我突然发现,
我的ans1好像会一直+,
而不会更新,
于是就成了这个样子:
```cpp
#include <cstdio>
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
int read(){
int x = 0;
char ch = getchar();
while (!isdigit(ch)) ch = getchar();
while (isdigit(ch)){
x = (x << 3) + (x << 1) + (ch ^ 48);
ch = getchar();
}
return x;
}
const int N = 1e4 + 5, M = 2e5 + 5;
int T, n, m;
int tot, to[M], nxt[M], head[N];
int du[N], num, ans1, ans2, sat[N], sun[N];
priority_queue <pair <int, int > > q;
bool flag[N];
void add(int u, int v){
to[++tot] = v, nxt[tot] = head[u], head[u] = tot;
}
void init(){
n = read(), m = read();
while (q.size()) q.pop();
memset(du, 0, sizeof(int) * (n + 1));
memset(head, 0, sizeof(int) * (n + 1));
memset(flag, 0, sizeof(int) * (n + 1));
num = ans1 = ans2 = tot = 0;
for (int i = 1; i <= m; i++){
int u = read(), v = read();
add(u, v); add(v, u);
du[u]++, du[v]++;
}
}
void solve(){
for (int i = 1; i <= n; i++) q.push(make_pair(-du[i], i));
while (q.size()){
int x = q.top().second; q.pop();
if (du[x] > num){
num = du[x]; ans1 = 0;
for (int i = 1; i <= n; i++){
if (!flag[i]) sat[++ans1] = i;
}
}
if (flag[x]) continue;
sun[++ans2] = x;
flag[x] = 1;
for (int i = head[x]; i; i = nxt[i]){
int y = to[i];
if (flag[y]) continue;
flag[y] = 1;
du[x]--, du[y]--;
q.push(make_pair(-du[y], y));
}
}
}
void print(){
printf("%d ", ans1);
for (int i = 1; i <= ans1; i++) printf("%d ", sat[i]);
printf("\n");
printf("%d ", ans2);
for (int i = 1; i <= ans2; i++) printf("%d ", sun[i]);
printf("\n");
}
int main(){
T = read();
while (T--){
init();
solve();
print();
}
return 0;
}
```
不抱希望的交了,
然后就A了...
其实这个算法的复杂度上限很大,
但是可能是由于随机数据加上近似解,
所以跑的并不慢.
这里就告诉我们要有梦想!
万一就过了呢!