ZigZagK的博客
[仙人掌DP]BZOJ4316【小C的独立集】题解
[仙人掌DP]BZOJ4316【小C的独立集】题解
2021年7月13日 19:57
BZOJ
查看标签

题目概述

图论小王子小C经常虐菜,特别是在图论方面,经常把小D虐得很惨很惨。

这不,小C让小D去求一个无向图的最大独立集,通俗地讲就是:在无向图中选出若干个点,这些点互相没有边连接,并使取出的点尽量多。小D虽然图论很弱,但是也知道无向图最大独立集是npc,但是小C很仁慈的给了一个很有特点的图: 图中任何一条边属于且仅属于一个简单环,图中没有重边和自环。小C说这样就会比较水了。

小D觉得这个题目很有趣,就交给你了,相信你一定可以解出来的。

解题报告

先建出圆方树,然后考虑树形DP。定义 $f_{i,0/1}$ 表示 $i$ 点是否选择的最大独立集,并且对于方点,将 $f_{i,0/1}$ 定义为与方点 $i$ 的顶点相邻的节点是否选择的最大独立集。

那么圆点就正常进行最大独立集DP,而方点需要进行进一步DP。

由于DFS树建圆方树时是按照深度顺序建边的,因此对于方点,按照加边顺序获取出所有儿子即为环上的顺序。定义 $F_{i,0/1,0/1}$ 表示前 $i$ 个节点中,第 $i$ 个节点是否选择,并且第一个节点是否选择的最大独立集。这样定义是因为更新方点信息时,我们需要用到第一个以及最后一个的状态。

最后 $\max\{f_{1,0},f_{1,1}\}$ 就是答案。

示例程序

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
#include<cstdio> #include<vector> #include<algorithm> using namespace std; const int maxn=100000,maxm=120000; int n,N,m,dfn[maxn+5],fa[maxn+5],lst[maxn+5];bool vis[maxm+5]; int E,lnk[maxn+5],nxt[maxm+5],son[maxm+5]; vector<int> e[maxn+5];int f[maxn][2],F[maxn+5][2][2]; inline void Add(int x,int y) {son[++E]=y;nxt[E]=lnk[x];lnk[x]=E;} void Cactus(int x,int pre=0){ dfn[x]=++dfn[0]; for (int j=lnk[x],u;j;j=nxt[j]) if ((u=son[j])!=pre) if (!dfn[u]) fa[u]=x,lst[u]=j,Cactus(u,x); else if (dfn[u]<dfn[x]){ N++;e[u].push_back(N);vis[j]=vis[j^1]=true; for (int i=x;i!=u;i=fa[i]) e[N].push_back(i),vis[lst[i]]=vis[lst[i]^1]=true; } } void DP(int x){ int si=e[x].size(); for (int j=0;j<si;j++) DP(e[x][j]); if (x>n){ for (int i=0;i<2;i++) for (int j=0;j<2;j++) F[0][i][j]=(i==j?f[e[x][0]][i]:-1e9); for (int i=1;i<si;i++) for (int j=0;j<2;j++){ F[i][j][0]=max(F[i-1][j][0],F[i-1][j][1])+f[e[x][i]][0]; F[i][j][1]=F[i-1][j][0]+f[e[x][i]][1]; } f[x][0]=F[si-1][0][0]; f[x][1]=-1e9; for (int i=0;i<2;i++) for (int j=0;j<2;j++) f[x][1]=max(f[x][1],F[si-1][i][j]); } else { for (int j=0;j<si;j++) f[x][1]+=f[e[x][j]][0];f[x][1]++; for (int j=0;j<si;j++) f[x][0]+=max(f[e[x][j]][0],f[e[x][j]][1]); } } int main(){ scanf("%d%d",&n,&m);N=n;E=1; for (int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),Add(x,y),Add(y,x); Cactus(1); for (int i=1;i<=n;i++) for (int j=lnk[i];j;j=nxt[j]) if (!vis[j] && dfn[son[j]]>dfn[i]) e[i].push_back(son[j]); DP(1);printf("%d\n",max(f[1][0],f[1][1])); return 0; }
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
本文写于 1358 天前,最后更新于 921 天前。
部分信息可能已经过时,博主也可能已经无法对其内容进行解答。
OK
  1. 1 Skyscape Plum - Melodic Artist
  2. 2 ほしのおとしもの ああああ
  3. 3 感情の摩天楼 ~ Cosmic Mind 上海アリス幻樂団
  4. 4 秘匿されたフォーシーズンズ 上海アリス幻樂団
  5. 5 Ideal and the Real 小西利樹
  6. 6 Undertale Toby Fox
  7. 7 First Steps Lena Raine
  8. 8 Mirror Temple (Mirror Magic Mix) Lena Raine / 2 Mello
  9. 9 City of Tears Christopher Larkin
  10. 10 Tower Of Heaven (You Are Slaves) Feint
Skyscape - Plum - Melodic Artist
00:00 / 00:00
An audio error has occurred, player will skip forward in 2 seconds.

作曲 : Jeong Min Jae

纯音乐,请欣赏