BelowLuminous edited 7 年，4 月前
- 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 那就是割边了。
总结：二分匹配的题都可以用最大流来解，在二分图中 有 “最小点覆盖集”和“最打独立集”，如果有了点权，那么就要用最大流(最小割)来解决 “最小点权覆盖集”(最小割)和“最大点权独立集”(最大流)问题。