【BZOJ1487】[HNOI2009]无归岛（仙人掌 DP）
题目：
分析：
题目中给定的图一定是一棵仙人掌（每条边最多属于一个环），证明如下：
先考虑单独一个岛的情况。第一，一个岛一定是一张「弦图」，即任意一个大小超过 3 的环都至少有 1 条弦。否则，这个环上不相邻的两点就不存在公共朋友，不符合「有一个公共朋友」。
第二，不存在有一条边被超过一个三元环包含。否则，这些三元环上与这条边相对的顶点都与这条边的两端点相邻，不符合「只有一个公共朋友」。
所以，每条边最多属于一个三元环。而由于大小超过 3 的环的弦一定存在于至少两个三元环中，所以不存在大小超过 3 的环。所以，在同一个岛中，每条边最多属于一个环，即为一个仙人掌。
现在，在每个岛（仙人掌）中选出一点与特定的另外两点相连，形成一个环。显然，每条新边都不可能和原本的仙人掌森林中的边形成环，所以这些新边在且仅在这个新环中。综上所述，原图是一个仙人掌。
那么这就是一个仙人掌 DP 的板子了（雾） 。设 (f[i][0/1]) 表示点 (i) 没选 / 选了时它的「子树」（见下文）内的最大权值。如果是一棵树，那么这就是一个非常简单的 DP （不会做的自觉面壁）。
下面这段比较难理解，不理解的话可以自己画个图手跑 Tarjan 。
考虑 Tarjan 求点双联通分量的过程。定义一个环的「根」为这个环上 dfs 序最小的点（就是建圆方树的时候把整个点双联通分量加进圆方树那个点 —— 只是以此为例说明，并不说明要建圆方树，下同）。如果一个环上所有的点的深度都大于等于某个点，那么这个环就在这个点的「子树」中，否则不算。即，一个环上只有这个环的「根」的子树包含这个环，这个环上被选中的点的权值在环上只算进根的 (f) 值。
当回溯到环的「根」时（就是把整个点双联通分量插入圆方树的时候），环上其他点的 (f) 值都已经计算完毕（再次强调，这些值都与这个环上的除了自己以外的点无关）。现在问题变成了：有一个环，选环上点 (i) 的权值是 (f[i][1])，不选的权值是 (f[i][0]) ，不能选相邻点，求最大能获得的权值。特别地，根的权值同样直接就是当前根的 (f) 值，因为要考虑这个根已经处理过的其他子树的权值。此处不理解的话参考树的做法。这个问题可以设 (g[i][0/1][0/1]) 表示当前考虑到第 (i) 个点，第一个点没选 / 选了，第 (i) 个点没选 / 选了。这个不会做的请继续面壁。
好像就这么多了？完结撒花~
代码：
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cctype>
using namespace std;
namespace zyt
{
template<typename T>
inline bool read(T &x)
{
char c;
bool f = false;
x = 0;
do
c = getchar();
while (c != EOF && c != '-' && !isdigit(c));
if (c == EOF)
return false;
if (c == '-')
f = true, c = getchar();
do
x = x * 10 + c - '0', c = getchar();
while (isdigit(c));
if (f)
x = -x;
return true;
}
template<typename T>
inline void write(T x)
{
static char buf[20];
char *pos = buf;
if (x < 0)
putchar('-'), x = -x;
do
*pos++ = x % 10 + '0';
while (x /= 10);
while (pos > buf)
putchar(*--pos);
}
const int N = 1e5 + 10, M = 2e5 + 10, INF = 0x3f3f3f3f;
int n, m, head[N], w[N], ecnt;
struct edge
{
int to, next;
}e[M << 1];
void add(const int a, const int b)
{
e[ecnt] = (edge){b, head[a]}, head[a] = ecnt++;
}
int dfn[N], low[N], dfncnt, f[N][2];
bool vis[M << 1];
void Tarjan(const int u, const int from)
{
static int sta[M << 1], top;
dfn[u] = low[u] = ++dfncnt;
f[u][0] = 0, f[u][1] = w[u];
for (int i = head[u]; ~i; i = e[i].next)
{
int v = e[i].to;
if (vis[i] || (i ^ 1) == from)
continue;
sta[top++] = i;
if (dfn[v])
low[u] = min(low[u], dfn[v]);
else
{
Tarjan(v, i);
low[u] = min(low[u], low[v]);
if (low[v] >= dfn[u])
{
if (sta[top - 1] == i)
{
f[u][0] += f[v][1], f[u][1] += f[v][0];
vis[sta[top - 1]] = vis[sta[top - 1] ^ 1] = true;
--top;
}
else
{
static int buf[N];
int cnt = 0, t;
do
{
t = sta[--top];
vis[t] = vis[t ^ 1] = true;
buf[cnt++] = e[t].to;
}
while (t != i);
static int dp[N][2][2];
dp[0][0][0] = dp[0][0][1] = f[u][0];
dp[0][1][0] = -INF, dp[0][1][1] = f[u][1];
for (int i = 1; i < cnt; i++)
for (int j = 0; j < 2; j++)
{
dp[i][j][0] = dp[i - 1][j][1] + f[buf[i]][0];
dp[i][j][1] = dp[i - 1][j][0] + f[buf[i]][1];
dp[i][j][1] = max(dp[i][j][1], dp[i][j][0]);
}
f[u][0] = dp[cnt - 1][0][1], f[u][1] = dp[cnt - 1][1][0];
}
}
}
}
f[u][1] = max(f[u][1], f[u][0]);
}
int work()
{
read(n), read(m);
memset(head, -1, sizeof(int[n + 1]));
for (int i = 0; i < m; i++)
{
int a, b;
read(a), read(b);
add(a, b), add(b, a);
}
for (int i = 1; i <= n; i++)
read(w[i]);
Tarjan(1, -1);
write(max(f[1][0], f[1][1]));
return 0;
}
}
int main()
{
freopen("1487.in", "r", stdin);
return zyt::work();
}