bzoj 4316: 小C的独立集 — 圆方树，dp
Contents
4316: 小C的独立集
Time Limit: 10 Sec Memory Limit: 128 MB
Description
图论小王子小C经常虐菜，特别是在图论方面，经常把小D虐得很惨很惨。
这不，小C让小D去求一个无向图的最大独立集，通俗地讲就是：在无向图中选出若干个点，这些点互相没有边连接，并使取出的点尽量多。
小D虽然图论很弱，但是也知道无向图最大独立集是npc，但是小C很仁慈的给了一个很有特点的图： 图中任何一条边属于且仅属于一个简单环，图中没有重边和自环。小C说这样就会比较水了。
小D觉得这个题目很有趣，就交给你了，相信你一定可以解出来的。
Input
第一行，两个数n， m，表示图的点数和边数。
第二~m+1行，每行两个数x，y，表示x与y之间有一条无向边。
Output
输出这个图的最大独立集。
Sample Input
5 6
1 2
2 3
3 1
3 4
4 5
3 5
1 2
2 3
3 1
3 4
4 5
3 5
Sample Output
2
HINT
100% n <=50000, m<=60000
Source
emmm直接搞出圆方树然后dp
我们只需要对于方点特殊处理
因为我们发现对于方点向上的更新，如果fa[x]取的话他会由f[x][0]更新，所以f[x][0]实际表示的是x儿子中头尾两个点不取的最优代价，我们可以再dp一下得到
同理，对于f[x][1]表示儿子中不相邻取法的最优代价，一样可以dp求得
#include<map>
#include<cmath>
#include<queue>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
#define inf 1000000007
#define ll long long
#define N 120010
inline int rd()
{
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int n,m,nn;
int dfn[N],tim,fa[N],len[N];
bool vs[N];
struct cst
{
int lj[N],fro[N],to[N],cnt=0;
void add(int a,int b){fro[++cnt]=lj[a];to[cnt]=b;lj[a]=cnt;}
int f[N][2],s[N],sz;
int g[N][2];//表示第i个儿子选或者不选的最大个数
void sol(int x)
{
sz=0;
for(int i=lj[x];i;i=fro[i]) s[++sz]=to[i];
if(sz==2)
{
f[x][0]=f[s[1]][0]+f[s[2]][0];
f[x][1]=max(f[s[1]][0]+f[s[2]][0],max(f[s[1]][0]+f[s[2]][1],f[s[1]][1]+f[s[2]][0]));
return;
}
g[1][0]=f[s[1]][0];g[1][1]=-inf;
for(int i=2;i<=sz;i++)
{
g[i][1]=g[i-1][0]+f[s[i]][1];
g[i][0]=max(g[i-1][1],g[i-1][0])+f[s[i]][0];
}
f[x][0]=g[sz][0];
g[1][0]=f[s[1]][0];g[1][1]=f[s[1]][1];
for(int i=2;i<=sz;i++)
{
g[i][1]=g[i-1][0]+f[s[i]][1];
g[i][0]=max(g[i-1][1],g[i-1][0])+f[s[i]][0];
}
f[x][1]=max(g[sz][0],g[sz][1]);
}
void dfs(int x)
{
f[x][0]=0;
f[x][1]=(x<=nn);
for(int i=lj[x];i;i=fro[i])
{
dfs(to[i]);
if(x<=nn)
{
f[x][0]+=max(f[to[i]][0],f[to[i]][1]);
f[x][1]+=f[to[i]][0];
}
}
if(x>nn) sol(x);
}
void work()
{
dfs(1);
printf("%d\n",max(f[1][0],f[1][1]));
}
}T;
int lj[N],fro[N],to[N],cnt;
void add(int a,int b){fro[++cnt]=lj[a];to[cnt]=b;lj[a]=cnt;}
void tarjan(int x)
{
dfn[x]=++tim;
for(int i=lj[x],tx;i;i=fro[i])
{
if(to[i]==fa[x]) continue;
if(!dfn[to[i]]) fa[to[i]]=x,tarjan(to[i]);
else if(dfn[to[i]]<dfn[x])
{
len[++n]=dfn[x]-dfn[to[i]]+1;
fa[n]=to[i];
T.add(to[i],n);
tx=x;
while(tx^to[i])
{
T.add(n,tx);
vs[tx]=1;
tx=fa[tx];
}
}
}
if(!vs[x]) T.add(fa[x],x);
tim--;
}
int main()
{
nn=n=rd();m=rd();
for(int i=1,x,y;i<=m;i++)
{
x=rd();y=rd();
add(x,y);add(y,x);
}
tarjan(1);
T.work();
return 0;
}
发表评论