仙人掌DP
记f[i][0/1]表示i取不取，子仙人掌的最大答案。树边直接转移，环边扫一圈转移。
感觉自己很智障，DP方程没什么问题，倒是tarjan写挂了???直接把栈里剩下的东西拿来当环上的东西也是没救了，才发现原来会有一些还没用的环留在栈里……
#include<cstdio> #include<algorithm> #define N 500005 #define cmin(u,v) ((u)>(v)?(u)=(v):0) using namespace std; namespace runzhe2000 { const int INF = 1<<29; int n, m, ecnt = 1, last[N], dfn[N], low[N], timer, sta[N], stacnt, f[N][2], fa[N]; struct edge{int next, to;}e[N<<1]; void addedge(int a, int b) { e[++ecnt] = (edge){last[a], b}; last[a] = ecnt; } void tarjan(int x, int fae) { dfn[x] = low[x] = ++timer; for(int i = last[x]; i; i = e[i].next) { if((i^1) == fae) continue; int y = e[i].to; if(!dfn[y]) { fa[y] = x; tarjan(y, i); cmin(low[x], low[y]); if(low[y] > dfn[x]) // tree { f[x][1] += f[y][0]; f[x][0] += max(f[y][1], f[y][0]); } } else if(low[y] == dfn[x]) // ring { stacnt = 0; for(int i = y; i != x; i = fa[i]) sta[++stacnt] = i; int g[2]; g[0] = g[1] = 0; for(int i = 1; i <= stacnt; i++) { int g0 = g[0], g1 = g[1]; g[1] = g0 + f[sta[i]][1]; g[0] = max(g0, g1) + f[sta[i]][0]; } f[x][0] += max(g[0], g[1]); g[0] = -INF; g[1] = 0; for(int i = 1; i <= stacnt; i++) { int g0 = g[0], g1 = g[1]; g[1] = g0 + f[sta[i]][1]; g[0] = max(g0, g1) + f[sta[i]][0]; } f[x][1] += g[0]; } else cmin(low[x], dfn[y]); } f[x][1]++; } void main() { scanf("%d%d",&n,&m); for(int i = 1, a, b; i <= m; i++) { scanf("%d%d",&a,&b); addedge(a, b); addedge(b, a); } tarjan(1,0); printf("%d\n",max(f[1][1], f[1][0])); } } int main() { runzhe2000::main(); }