Knights of the Round Table (补图+点连通分量缩点板子+二分图判定奇环)

    科技2022-07-16  98

    http://poj.org/problem?id=2942


    思路:首先考虑建边,但是会发现直接建边很难处理。

    那么考虑通过能相邻的图去建立边.建完边后结合题意,题目说要求一些骑士永远不可能去开会。开会的要求有一个>=3的奇环。

    所以题目问的是哪些骑士是不在任何一个奇环里的。

    所以考虑把补图上所有的缩点后的点联通分量里面判一下奇环。

    奇环的判定也就是染色法判定是不是二分图。

    这个题大概调了5小时。

    做了之后发现点连通分量的板子是不一样的,因为割点是属于多个连通分量里面的,不能直接按照求强连通分量的缩点那样直接弹出栈。

    另外注意在主函数里面把每个dcc[]打上对应的编号,然后在判奇数环的时候注意在补图上判奇数环,dcc[]里面是没有连边关系的。同时注意遍历点的时候是要在同一个dcc[]里的

    提供一组数据:

    7 12 1 7 2 1 3 6 7 6 1 4 4 7 4 2 1 5 2 3 2 7 6 5 5 3 0 0 ans:7

    http://poj.org/bbs?problem_id=2942(更多的见discuss)

    Processed: 0.010, SQL: 8