CodeForces#19 E

这是道好题啊。。。想想麻烦。。做做更麻烦。。
题目很简洁,给你一个图,求哪些边删掉之后能变成二分图。。
额。。我WA了N次。。比赛的时候肯定来不及。。。
慢慢分析吧。。
首先求生成树,然后对每个点2-染色,
那么如果删非树边的话,显然任何点的颜色都不会变,那么如果两端颜色一样的非树边有0条,所有非树边都可以删,有1条,只有这条可以删,2条或以上,都不能删。。
如果删树边的话,显然必须要搞翻所有的奇环,分析一下什么情况下一个树中会出现奇环。。
某个两端颜色一样的非树边造成的奇环。。
一个两端颜色一样的非树边和一个两端不一样的非树边造成的奇环。。
那么把这个树树链剖分一下。。对每个两端颜色一样的非树边的两点之间的路径+1,显然要删的树边上的权值一定要等于非树边的数量。。
然后对每个两端颜色不一样的非树边的两点之间的路径+1,显然要删掉树边不能在被两端颜色一样的非树边的两点间的路径跨越的情况下再被这个不一样的非树边的两点之间的路径跨越。。
然后维护两个树链剖分。。分别搞树边和非树边。。就没什么问题了。。
写的累死晕。。。
我发现还是我在codeforces上英文的说明更清楚一点啊囧。。。
It’s a interesting problem.If you for every edge, 
try to remove it and check if it is a 
bipartite 
graph..I think it will get TLE..so let’s analysis 
the property of bipartite graph..
It should never contain a cycle of odd length…
and it can be 2-colored..
so first build a spanning forest for the graph..
and do the 2-color on it(Tree can be 2-colored).
for convenience.
Let TreeEdge={all edge in forest}
NotTreeEdge={All edge}/TreeEdge
ErrorEdge={all edge that two endpoint have the same color..}
NotErorEdge=NotTreeEdge/ErroEdge..
First,consider a edge form NotTreeEdge,remove it 
can’t change any node’s color..so..if |ErrorEdge|=0 of course we can remove all NotTreeEdgeif =1 we just can remove the ErrorEdgeif >1 we can’t remove any from NotTreeEdge
Now,Let consider a Edge e from TreeEdge..
Let Path(Edge e)=the path in forest between e’s two endpoints..
if there is a Edge e’ from ErrorEdge that Path(e’) 
didn’t  go through e..it will destroy the bipartite 
graph..
if there is a Edge e’ from ErrorEdge that Path(e’) go through e and there is a Edge e” from NotErrorEdge that Path(e”) go through e..it will also destroy the bipartite graph..
so now we need to know for every edge,how many such path go through it..it require a data structure…
one way is to use heavy-light decomposition then we can update every path in O(LogN^2)…
another way is to use Link-Cut Tree..It can do the same in O(LogN)….
Code:
http://www.ideone.com/dPS5N

8 thoughts on “CodeForces#19 E

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>