bzoj 4316: 小C的独立集 — 圆方树,dp

  • 2018-05-25
  • 0
  • 0

 

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

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求得

 

评论

还没有任何评论,你来说两句吧