Description
图论小王子小 C 经常虐菜, 特别是在图论方面, 经常把小 D 虐得很惨很惨.
这不, 小 C 让小 D 去求一个无向图的最大独立集, 通俗地讲就是: 在无向图中选出若干个点, 这些点互相没有边连接, 并使取出的点尽量多.
小 D 虽然图论很弱, 但是也知道无向图最大独立集是 npc, 但是小 C 很仁慈的给了一个很有特点的图: 图中任何一条边属于且仅属于一个简单环, 图中没有重边和自环. 小 C 说这样就会比较水了.
小 D 觉得这个题目很有趣, 就交给你了, 相信你一定可以解出来的.
题解
可以考虑用仙人掌的做法来弄, 我们可以不用把圆方树给建出来
直接在 tarjan 中做, 设 f[i][0/1] 表示当前点为 i 选或不选 i 的子树的最大独立集
转移的话和一般的树形 dp 差不多, 这样子做完就相当于把环给单独拎出来考虑
代码
- #include <cstdio>
- #include <iostream>
- #define N 60010
- using namespace std;
- struct edge{int to,from;}e[N*3];
- int n,m,cnt=1,Fa[N],f[N][2],dfn[N],low[N],head[N];
- void insert(int x,int y)
- {
- e[++cnt].to=y,e[cnt].from=head[x],head[x]=cnt;
- e[++cnt].to=x,e[cnt].from=head[y],head[y]=cnt;
- }
- void dp(int x,int y)
- {
- int r0,r1,f0=0,f1=0;
- for (int i=y;i!=x;i=Fa[i]) r0=f0+f[i][0],r1=f1+f[i][1],f0=max(r0,r1),f1=r0;
- f[x][0]+=f0,f0=0,f1=-1e9;
- for (int i=y;i!=x;i=Fa[i]) r0=f0+f[i][0],r1=f1+f[i][1],f0=max(r0,r1),f1=r0;
- f[x][1]+=f1;
- }
- void dfs(int x,int fa)
- {
- dfn[x]=low[x]=++dfn[0],f[x][1]=1,f[x][0]=0,Fa[x]=fa;
- for (int i=head[x];i;i=e[i].from)
- {
- if (!dfn[e[i].to]) dfs(e[i].to,x),low[x]=min(low[x],low[e[i].to]); else if (e[i].to!=fa) low[x]=min(low[x],dfn[e[i].to]);
- if (low[e[i].to]>dfn[x]) f[x][1]+=f[e[i].to][0],f[x][0]+=max(f[e[i].to][0],f[e[i].to][1]);
- }
- for (int i=head[x];i;i=e[i].from) if (Fa[e[i].to]!=x&&dfn[x]<dfn[e[i].to]) dp(x,e[i].to);
- }
- int main()
- {
- scanf("%d%d",&n,&m);
- for (int i=1,x,y;i<=m;i++) scanf("%d%d",&x,&y),insert(x,y);
- dfs(1,0),printf("%d",max(f[1][0],f[1][1]));
- }
[树形 dp][Tarjan] Bzoj 4316 小 C 的独立集
来源: http://www.bubuko.com/infodetail-3158926.html