二分图问题资料整合处理(3):二分图问题常见模型

BelowLuminous edited 6 年,8 月前

  1. zoj1654
    题意:有一个N*M(N,M<=50)的棋盘,棋盘的每一格是三种类型之一:空地、草地、墙。机器人只能放在空地上。在同一行或同一列的两个机器人,若它们之间没有墙,则它们可以互相攻击。问给定的棋盘,最多可以放置多少个机器人,使它们不能互相攻击。
    分析:本题也是二分图匹配的一个经典题目。我们将每一行,每一列被墙隔开,且包含空地的连续区域称作“块”。显然,在一个块之中,最多只能放一个机器人,我们把这些块编上号。同样,把竖直方向的块也编上号,把每个横向块看作X部的点,竖向块看作Y部的点,若两个块有公共的空地,则在它们之间连边。于是,问题转化成这样的一个二分图。
    2.zoj1364/poj1325/Asia Beijing2002
    题意 机器调度问题 有两个机器A,B A有n种工作模式0…n-1 B有m种工作模式0…m-1 然后又k个任务要做 每个任务可以用A机器的模式i或b机器的模式j来完成 机器开始都处于模式0 每次换模式时都要重启 问完成所有任务机器至少重启多少次
    最基础的二分图最大匹配问题 对于每个任务把i和j之间连一条边就可以构成一个二分图 那么每个任务都可以对应一条边 那么现在就是要找最少的点 使这些点能覆盖所有的边 即点覆盖数
    3.zoj1140/poj1468/southeasterm Europe 2000
    题意:
    N个学生和P门课程,每个学生学习0, 1 或者多门课程,判断是否能从这些学生中选出P名学生,组成一个委员会,满足以下条件:
    (1)委员会中的每名学生代表一门不同的课程,只有学生学习了这门课程,他才可以代表这门课程
    (2)每个课程在委员会中必须有一名代表。
    分析:太水了,略。
    4.zoj2429/poj2125/northeastrem Europe 2003
    题意:
    N个点M条边的有向图,给出如下两种操作。
    删除点i的所有出边,代价是Ai。
    删除点j的所有入边,代价是Bj。
    求最后删除图中所有的边的最小代价。
    分析:首先我们根据题意,选点就能删除一些边, 那么这可以看成是“用点去覆盖边”, 这里无非是把边分成了2类,
    我们可以把原来的点进行拆点,那么就完完全全等价于“用点去覆盖边”,如果支付费用都为1,那么这就是”最小点覆盖集“问题,但这题费用不确定,那么这就是“最小点权覆盖集”问题, 借助二分匹配的思想,我们可以引入“最小割”来解决“最小点权覆盖”问题。
    建图:拆点,左点阵为情况2的点, 右点阵为情况1的点,右点阵跟汇点T连流量为W+,左点阵跟源点S连费用为W-,
    对于输入的边 连边 (u, v+n)费用为无穷大inf。跑一边最大流,求出最小费用。
    输出解:最要我们找到一个满足条件的割边集(注意不是所有割边, 因为有一条流已经经过了一条割边,那么下面一条割边就不用选了,这样费用才是最小的),那么就能输出解了。怎么找出割边呢?我们可以在残余网络里走流,如果有一条边是割边,那么之后就流不过去了,不是割边还能继续流,具体实现我们可以从源点S用dfs搜出能走到的点标记vis[] =1,
    那么对于边 只要 vis[u] = 1 && vis[v] = 0 那就是割边了。
    总结:二分匹配的题都可以用最大流来解,在二分图中 有 “最小点覆盖集”和“最打独立集”,如果有了点权,那么就要用最大流(最小割)来解决 “最小点权覆盖集”(最小割)和“最大点权独立集”(最大流)问题。

Comments