Luogu-4410 [HNOI2009]无归岛

时间:2021-05-24 23:26:26

裸的仙人掌最大独立子集,结果一个zz的错误让我调了好久...

\(-inf\)开始设为\(0x7fffffff\)结果\(A_i\)有负数一加就炸了

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=2e5+100,maxm=5e5+100,inf=200000000;
int n,m,v[maxm],nex[maxm],head[maxn],num=1,f[maxn][2],a,b,tim,dfn[maxn],fa[maxn],p[maxn];
void add(int x,int y){
v[++num]=y;
nex[num]=head[x];
head[x]=num;
v[++num]=x;
nex[num]=head[y];
head[y]=num;
}
void dp(int x,int y){
int z=y;
int u0=0,u1=0,v0,v1;
while(z!=x){
v1=u0+f[z][1],v0=u1+f[z][0];//交叉选择
u0=v0,u1=max(v0,v1);//可以不选
z=fa[z];
}
f[x][0]+=u1;
u0=-inf,u1=0,z=y;//因为这是环,若x选了,则y不能选
while(z!=x){
v1=u0+f[z][1],v0=u1+f[z][0];
u0=v0,u1=max(v0,v1);
z=fa[z];
}
f[x][1]+=u0;//最后一个也不能选
}
void tarjan(int x){
dfn[x]=++tim;
for(int i=head[x];i;i=nex[i])
if(!dfn[v[i]])
fa[v[i]]=x,tarjan(v[i]);
f[x][1]=p[x];
for(int i=head[x];i;i=nex[i])
if(dfn[v[i]]>dfn[x]&&fa[v[i]]!=x)
dp(x,v[i]);//环内dp
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++)
scanf("%d%d",&a,&b),add(a,b);
for(int i=1;i<=n;i++)
scanf("%d",&p[i]);
tarjan(1);
printf("%d\n",max(f[1][0],f[1][1]));
return 0;
}