HDU 2454 Degree Sequence of Graph G
Havel定理判定简单图 被上下界网络流烦傻了，暂时不想写代码太长的题。 虽然是一道水题，但也是建立在一定理论基础上的。 再科普一下简单图，没有重边没有自环的图就是简单图。区别有向图和无向图，也就是说，有向图的反向边不算重边。 给定一个非负整数序列{dn}，若存在一个无向图使得图中各点的度与此序列一一对应，则称此序列可图化。进一步，若图为简单图，则称此序列可简单图化 可图化的判定： ( \sum_{i=1}^{n}d_{i} mod 2 == 0 ) 。关于具体图的构造，我们可以简单地把奇数度的点配对，剩下的全部搞成自环。 可简单图化的判定（Havel定理）： 把序列排成不增序，即 ( d_1 \geq d_2 \geq \ldots \geq d_n )，则d可简单图化当且仅当 ( d’ = \left{ d_2-1 , d_…