bipartite专题

hdu 5313 Bipartite Graph

题意: Soda有一个n个点m条边的二分图, 他想要通过加边使得这张图变成一个边数最多的完全二分图. 于是他想要知道他最多能够新加多少条边. 注意重边是不允许的. 官方题解: 分析:首先用bfs染色找出每一个连通分量的黑点,白点的数量,然后求出X*Y的最大值。 直接写的dp超时,用了题解中提到的bitset,终于过了。。。 第一次发现bitse

计算二分图(bipartite graph)交叉点(crossing)的数量

对于一个二分图,如果图的两个部分的顶点都按照顺序分别排列在一对平行线上,如下图,如何计算这个二分图的边有多少个交叉点呢?需要注意两点:1. 在图的顶点处连接的边不认为产生了交叉点,如下图在c、d、B和D点连接的边;2. 如果交叉点有两条以上边经过,这些边中的每对边都要算作产生了一个交叉点,如下图Bd、Cc和Db算作产生了3个交叉点。 那么这个图共有多少个交叉点呢?数一数就可以得出结论,答案是5个