自动搬运

查看原文

来自洛谷，原作者为

	Umbrella_Leaf 曹刘生子，当如孙仲谋。

搬运于2025-08-24 22:15:10，当前版本为作者最后更新于2023-04-21 11:33:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

讲一个其他题解都没有的做法，甚至不需要开空间。

我真没用空间啊，是交互库开的关我啥事啊

题意简述

给定一张无向图，让你求最大权独立集。

但是最大权独立集是 NPC 问题，所以这个图有特殊的构造方式：

初始只有一个点 $0$，从 $1$ 到 $n-1$ 依次加入点，每次加入点 $i$ 时有三种选择：

0. 给定 $j$，将 $i$ 与 $j$ 连边；
1. 给定 $j$，将 $i$ 与 $j$ 的所有邻居连边；
2. 给定 $j$，将 $i$ 与 $j$ 和 $j$ 的所有邻居连边。

$n\le 10^5$。

思路分析

我们考虑倒过来做，从大到小依次删掉点 $i$。

分类讨论：

1. $i$ 与 $j$ 连边。我们先把答案加上 $a_i$，然后 $a_j\gets a_j-a_i$。但是可能会 $a_j<a_i$，此时一定不会选 $a_j$，因此应该是 $a_j\gets \max(a_j-a_i,0)$。

2. $i$ 与 $j$ 的所有邻居连边。此时 $i$ 和 $j$ 的所有出边相同，因此他们是否被选也一定相同，所以 $a_j\gets a_j+a_i$。

3. $i$ 与 $j$ 和 $j$ 的所有邻居连边。此时 $i$ 和 $j$ 只能选一个，并且选哪个对其他点来说是一样的，所以 $a_j\gets \max(a_j,a_i)$。

然后就过了，时间复杂度 $O(n)$。

代码展示

$b_0$ 没用，所以可以用来存答案。

#include<bits/stdc++.h>
using namespace std;
int findSample(int n,int* a,int* b,int* opt){
	b[0]=0;
	while(--n)
		if(!opt[n])b[0]+=a[n],a[b[n]]=max(0,a[b[n]]-a[n]);
		else if(opt[n]==1)a[b[n]]+=a[n];
		else a[b[n]]=max(a[b[n]],a[n]);
	return b[0]+a[0];
}

Update：有同学发现上面的代码会用到编译器的临时空间，写了个疑似不需要辅助空间的代码：

int findSample(int n, int a[], int b[], int opt[]) {
    *b = 0;
    while (--n) {
        opt += n;
        if (*opt) {
            if (*opt &= 1) {
                a += n, *opt = *a, a -= n;
                b += n, a += *b;
                *a += *opt;
                a -= *b, b -= n;
            } else {
                a += n, *opt = *a, a -= n;
                b += n;
                a += *b, *opt -= *a, a -= *b;
                *opt *= -1;
                *opt >>= 31;
                if (*opt) {
                    a += n, *opt = *a, a -= n;
                    a += *b, *a = *opt, a -= *b;
                }
                b -= n;
            }
        } else {
            a += n, *b += *a, a -= n;
            b += n;
            a += n, *opt = *a, a -= n;
            a += *b;
            *a -= *opt;
            *opt = *a, *opt >>= 31;
            if (*opt) *a = 0;
            a -= *b;
            b -= n;
        }
        opt -= n;
    }
    return *b += *a;
}