[BZOJ 4316][サボテン][DP]小さなCの独立集
サボテンだと気づいた
ツリーDPを考慮し、息子がループでなければツリーDP、そうでなければループを抽出し、1040の方法を参照する.
ツリーDPを考慮し、息子がループでなければツリーDP、そうでなければループを抽出し、1040の方法を参照する.
#include
#include
#include
#define N 100010
using namespace std;
int n,m,cnt,u,v,g,t;
int G[N],fa[N],dfn[N],low[N],vis[N],Q[N],dpt[N];
int f[N][2],w[N][2];
struct edge{
int t,nx;
}E[N<<2];
inline void reaD(int &x){
char c=getchar(); x=0;
for(;c>57||c<48;c=getchar());for(;c>=48&&c<=57;x=x*10+c-48,c=getchar());
}
inline int max(const int &a,const int &b){
return ainline void Insert(int x,int y){
E[++cnt].t=y; E[cnt].nx=G[x]; G[x]=cnt;
E[++cnt].t=x; E[cnt].nx=G[y]; G[y]=cnt;
}
inline void DP(int x,int y){
t=0;
for(int i=y;i!=fa[x];i=fa[i]) Q[++t]=i;
w[0][0]=w[0][1]=0;
for(int i=1;i<=t;i++)
w[i][0]=max(w[i-1][0],w[i-1][1])+f[Q[i]][0],
w[i][1]=w[i-1][0]+f[Q[i]][1];
int k=w[t][0]; w[0][0]=-1;
for(int i=1;i<=t;i++)
w[i][0]=max(w[i-1][0],w[i-1][1])+f[Q[i]][0],
w[i][1]=w[i-1][0]+f[Q[i]][1];
f[x][1]=w[t][1];
f[x][0]=k;
}
void dfs(int x,int p){
dfn[x]=low[x]=++g; vis[x]=1; fa[x]=p; dpt[x]=dpt[p]+1;
f[x][0]=0; f[x][1]=1;
for(int i=G[x];i;i=E[i].nx)
if(E[i].t!=p){
if(!vis[E[i].t]){
dfs(E[i].t,x);
if(low[E[i].t]>dfn[x])
f[x][0]+=max(f[E[i].t][0],f[E[i].t][1]),
f[x][1]+=f[E[i].t][0];
low[x]=min(low[x],low[E[i].t]);
}
else low[x]=min(low[x],dfn[E[i].t]);
}
for(int i=G[x];i;i=E[i].nx)
if(E[i].t!=fa[x]&&low[E[i].t]==dfn[x]&&dpt[x]+1!=dpt[E[i].t]) DP(x,E[i].t);
}
int main(){
reaD(n); reaD(m);
for(int i=1;i<=m;i++)
reaD(u),reaD(v),Insert(u,v);
dfs(1,0);
printf("%d
",max(f[1][0],f[1][1]));
return 0;
}