【BZOJ】4316:|【BZOJ】4316: 小C的独立集静态仙人掌【BZOJ】4316:小C的独立集静态仙

【题意】给定仙人掌图，求最大独立集（选择最大的点集使得点间无连边）。n<=50000,m<=60000。
【算法】DFS处理仙人掌图
【题解】参考：【BZOJ】1023: [SHOI2008]cactus仙人掌图
对仙人掌进行无向图的点双连通分量Tarjan算法，树边正常DP，环边(low[y]<=dfn[x])无视。
每个环在其深度最小的点整体处理（找到(u,v)只须fa[v]≠u&&dfn[y]>dfn[x]）。
DP的做法参考：【BZOJ】1040: [ZJOI2008]骑士环套树DP

文章图片

文章图片

#include #include #include using namespace std; int read(){ char c; int s=0,t=1; while(!isdigit(c=getchar()))if(c=='-')t=-1; do{s=s*10+c-'0'; }while(isdigit(c=getchar())); return s*t; } const int maxn=100010; struct edge{int v,from; }e[maxn*2]; int n,m,tot,first[maxn],fa[maxn],f[maxn][2],g[maxn][2]; int dfn[maxn],low[maxn],dfsnum=0; void insert(int u,int v){tot++; e[tot].v=v; e[tot].from=first[u]; first[u]=tot; }void solve(int u,int v){ int cnt=0; for(int i=v; i!=fa[u]; i=fa[i]){cnt++; g[cnt][0]=f[i][0]; g[cnt][1]=f[i][1]; } for(int i=2; i<=cnt; i++){ g[i][0]+=max(g[i-1][0],g[i-1][1]); g[i][1]+=g[i-1][0]; } f[u][0]=g[cnt][0]; cnt=0; for(int i=v; i!=fa[u]; i=fa[i]){cnt++; g[cnt][0]=f[i][0]; g[cnt][1]=f[i][1]; } g[1][1]=-0x3f3f3f3f; for(int i=2; i<=cnt; i++){ g[i][0]+=max(g[i-1][0],g[i-1][1]); g[i][1]+=g[i-1][0]; } f[u][1]=g[cnt][1]; } void tarjan(int x,int father){ dfn[x]=low[x]=++dfsnum; f[x][0]=0; f[x][1]=1; for(int i=first[x]; i; i=e[i].from)if(i!=father){ int y=e[i].v; if(!dfn[y]){ fa[y]=x; tarjan(y,i); low[x]=min(low[x],low[y]); }else low[x]=min(low[x],dfn[y]); if(low[y]>dfn[x]){ f[x][0]+=max(f[y][0],f[y][1]); f[x][1]+=f[y][0]; } } for(int i=first[x]; i; i=e[i].from)if(fa[e[i].v]!=x&&dfn[e[i].v]>dfn[x])solve(x,e[i].v); } int main(){ n=read(); m=read(); for(int i=1; i<=m; i++){ int u=read(),v=read(); insert(u,v); insert(v,u); } tarjan(1,0); printf("%d",max(f[1][0],f[1][1])); return 0; }

View Code
【【BZOJ】4316:|【BZOJ】4316: 小C的独立集静态仙人掌】转载于:https://www.cnblogs.com/onioncyc/p/8312843.html