[BZOJ4316][仙人掌][DP]小C的独立集

2019-11-06 06:31:56

字体：大中小

来源：转载

供稿：网友

注意到图是个仙人掌

考虑树形DP，如果儿子不是环，那么就树形DP，否则就把环提出来，参照1040的做法。

#include <cstdio>#include <iostream>#include <algorithm>#define N 100010using 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 a<b?b:a;}inline 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/n",max(f[1][0],f[1][1])); return 0;}

上一篇：控制台程序的返回值为 -1073741515的错误分析

下一篇：Fibonacci数列算法的几种实现方式与比较