挑战程序竞赛系列（26）：3.5二分图匹配（1）
挑战程序竞赛系列（26）：3.5二分图匹配（1）
用户1147447
发布于 2019-05-26 09:25:31
发布于 2019-05-26 09:25:31
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434647
挑战程序竞赛系列（26）：3.5二分图匹配（1）
详细代码可以fork下Github上leetcode项目，不定期更新。
练习题如下：
POJ 1274: The perfect Stall
熟悉了最大流，二分图匹配就易如反掌，之所以是个最大流问题，可以想想增广路径是如何分配流量的，传说中的反悔重走在这里运用的淋漓尽致。
步骤：
- 新建源点s和汇点t
- 源点s与所有奶牛顶点连接，且边权为1，这样能够保证匹配时不漏掉任何一头牛（每头牛都有机会在自己想要的牛奶棚产奶）。
- 所有牛奶棚与汇点t连接，边权为1，把所有产生的奶按照一单位运输到最终目的地。（一条流水线）
- 奶牛与喜爱的牛奶棚建立连接，边权为1，增广路径在此处发挥了极其大的价值，每次找一条增广路径时，可以让已经匹配的边逆流（传说中的返回重来），只要能找到一条，最大匹配数+1。
可以用一般的最大流算法实现：
class Edge{
int from;
int to;
int cap;
int rev;
public Edge(int from, int to, int cap, int rev){
this.from = from;
this.to = to;
this.cap = cap;
this.rev = rev;
}
}
List<Edge>[] g;
int V;
void solve() {
Scanner in = new Scanner(System.in);
while (in.hasNext()){
int N = in.nextInt();
int M = in.nextInt();
V = N + M + 2;
int s = 0, t = N + M + 1;
g = new ArrayList[V];
for (int i = 0; i < V; ++i) g[i] = new ArrayList<Edge>();
for (int i = 1; i <= N; ++i){
addEdge(s, i, 1);
}
for (int j = 1; j <= M; ++j){
addEdge(j + N, t, 1);
}
for (int i = 1; i <= N; ++i){
int m = in.nextInt();
for (int j = 0; j < m; ++j){
int stall = in.nextInt();
addEdge(i, stall + N, 1);
}
}
System.out.println(fordFulkerson(s, t));
}
in.close();
}
public void addEdge(int from, int to, int cap){
g[from].add(new Edge(from, to, cap, g[to].size()));
g[to].add(new Edge(to, from, 0, g[from].size() - 1));
}
static final int INF = 1 << 30;
public int fordFulkerson(int s, int t){
int flow = 0;
for (;;){
int f = dfs(s, t, INF, new boolean[V]);
if (f > 0) flow += f;
else break;
}
return flow;
}
public int dfs(int s, int t, int f, boolean[] visited){
if (s == t) return f;
visited[s] = true;
for (Edge e : g[s]){
int to = e.to;
if (!visited[to] && e.cap > 0){
int d = dfs(to, t, Math.min(f, e.cap), visited);
if (d > 0){
e.cap -= d;
g[to].get(e.rev).cap += d;
return d;
}
}
}
return 0;
}
void run() throws Exception {
solve();
}
public static void main(String[] args) throws Exception {
new SolutionDay21_P1274().run();
}但其实每次找寻增广路径，流量都只会+1，所以只要找到增广路径即可，无需返回流量，简化版的二分图如下：
List<Integer>[] g;
int V;
int N;
void solve() {
Scanner in = new Scanner(System.in);
while (in.hasNext()){
N = in.nextInt();
int M = in.nextInt();
V = N + M;
g = new ArrayList[V];
for (int i = 0; i < V; ++i) g[i] = new ArrayList<Integer>();
for (int i = 0; i < N; ++i){
int m = in.nextInt();
for (int j = 0; j < m; ++j){
int stall = in.nextInt();
addEdge(i, stall + N - 1);
}
}
System.out.println(bipartite_matching());
}
in.close();
}
public void addEdge(int from, int to){
g[from].add(to);
g[to].add(from);
}
public int bipartite_matching(){
int res = 0;
matching = new int[V];
Arrays.fill(matching, -1);
for (int i = 0; i < N; ++i){
if (matching[i] < 0){
if (dfs(i, new boolean[V])){
res ++;
}
}
}
return res;
}
int[] matching;
public boolean dfs(int v, boolean[] used){
used[v] = true;
for (int u : g[v]){
int w = matching[u];
if (w < 0 || !used[w] && dfs(w, used)){
matching[u] = v;
matching[v] = u;
return true;
}
}
return false;
}和最大流算法稍微有些区别，用matching来记录匹配时的状态，used来记录是否已经反悔（每人只能反悔一次）。
POJ 2112: Optimal Milking
思路：二分+最大流，先计算所有奶牛到每台机器的最短距离，采用warshall_floyd算法，接着二分猜最长距离的最短距离边，如果猜的值够大，那么所有的奶牛都能找到机器。而如果猜的值较小，那么必然有几头奶牛不能成功找到对应的机器。如何表示是否有奶牛匹配到对应的机器呢？采用二分图匹配，建立源点s和汇点t，如果最终最大流 == 奶牛数，说明当前值可以进一步缩小。
代码如下：
int[][] graph;
int V;
int K;
int C;
int M;
void solve() {
K = ni();
C = ni();
M = ni();
V = K + C + 2;
graph = new int[K + C][K + C];
for (int i = 0; i < K + C; ++i){
for (int j = 0; j < K + C; ++j){
int d = ni();
graph[i][j] = d != 0 ? d : INF;
}
}
int n = K + C;
for (int k = 0; k < n; ++k){
for (int i = 0; i < n; ++i){
for (int j = 0; j < n; ++j){
graph[i][j] = Math.min(graph[i][j], graph[i][k] + graph[k][j]);
}
}
}
int lb = 0, ub = 200 * n;
while (ub - lb > 1){
int mid = (ub + lb) / 2;
if (check(mid)) ub = mid;
else lb = mid;
}
out.println(ub);
}
public boolean check(int limit){
g = new ArrayList[V];
for (int i = 0; i < V; ++i) g[i] = new ArrayList<Edge>();
int s = 0;
int t = V - 1;
//源点到奶牛
for (int id = 0; id < C; ++id){
addEdge(s, id + 1 + K, 1);
}
//机器到汇点
for (int id = 0; id < K; ++id){
addEdge(id + 1, t, M);
}
for (int cow = 0; cow < C; ++cow){
for (int ml = 0; ml < K; ++ml){
if (graph[cow + K][ml] <= limit){
addEdge(cow + K + 1, ml + 1, 1);
}
}
}
return maxFlow(s, t) == C;
}
public void addEdge(int from, int to, int cap){
g[from].add(new Edge(from, to, cap, g[to].size()));
g[to].add(new Edge(to, from, 0, g[from].size() - 1));
}
/************dinic************/
class Edge{
int from;
int to;
int cap;
int rev;
public Edge(int from, int to, int cap, int rev){
this.from = from;
this.to = to;
this.cap = cap;
this.rev = rev;
}
}
static final int INF = 1 << 28;
List<Edge>[] g;
public int maxFlow(int s, int t){
int flow = 0;
for (;;){
bfs(s);
if (level[t] < 0) break;
int f = 0;
while ((f = dfs(s, t, INF, new boolean[V])) > 0) flow += f;
}
return flow;
}
int[] level;
public void bfs(int s){
level = new int[V];
Arrays.fill(level, -1);
level[s] = 0;
Queue<Integer> queue = new LinkedList<Integer>();
queue.offer(s);
while (!queue.isEmpty()){
int v = queue.poll();
for (Edge e : g[v]){
int to = e.to;
if (level[to] < 0 && e.cap > 0){
level[to] = level[v] + 1;
queue.offer(to);
}
}
}
}
public int dfs(int s, int t, int f, boolean[] visited){
if (s == t) return f;
visited[s] = true;
for (Edge e : g[s]){
int to = e.to;
if (!visited[to] && e.cap > 0 && level[e.from] + 1 == level[to]){
int d = dfs(to, t, Math.min(f, e.cap), visited);
if (d > 0){
e.cap -= d;
g[to].get(e.rev).cap += d;
return d;
}
}
}
return 0;
}POJ 1486: Sorting Slides
此题用贪心是错误的，具体思路如下：
每次找到出度或者入度为1的（也就是框上只有一个点，或者点只在一个框上的），把这样的点和框一起删除，在继续找，直到找不出为止。
举个反例：
5
1 4 1 4
2 7 2 7
5 11 5 11
8 13 9 14
9 14 8 13
3 3
3 3
6 6
10 10
12 12
实际输出：
(c,3)
贪心结果为：none画图就能明白，虽然在此case下，所有的顶点出度都大于1，所以贪心会认为没有确定的边，但是如果你枚举某一条边，你会发现它有一种情况是矛盾的，进而推出了一条唯一确定的边。
此题的思路得反一反，首先明确一点，如果所有边都存在的情况下，必然是完美匹配图，所以不管怎么匹配，最终匹配的结果一定是n，那么当删除一条确定关系的边会发生什么？容易想象，如果删除一条边，导致该二分图不再完美，那么该条边连接的slide和point是确定的，否则可删可不删。
代码如下：
class Point{
int x;
int y;
public Point(int x, int y){
this.x = x;
this.y = y;
}
}
class Slide{
int minX;
int maxX;
int minY;
int maxY;
public Slide(int minX, int maxX, int minY, int maxY){
this.minX = minX;
this.maxX = maxX;
this.minY = minY;
this.maxY = maxY;
}
public boolean contain(Point point){
int x = point.x;
int y = point.y;
return minX < x && x < maxX && minY < y && y < maxY;
}
}
Slide[] slides;
Point[] points;
int[] sliding;
int V;
void solve() {
int cnt = 0;
while (true){
int n = ni();
if (n == 0) break;
++cnt;
V = 2 * n;
init(V);
slides = new Slide[n];
points = new Point[n];
for (int i = 0; i < n; ++i) {
int minX = ni();
int maxX = ni();
int minY = ni();
int maxY = ni();
slides[i] = new Slide(minX, maxX, minY, maxY);
}
for (int i = 0; i < n; ++i) {
int x = ni();
int y = ni();
points[i] = new Point(x, y);
}
sliding = new int[n];
Arrays.fill(sliding, -1);
for (int i = 0; i < n; ++i){
for (int j = 0; j < n; ++j){
if (slides[i].contain(points[j])){
clear();
for (int k = 0; k < n; ++k){
for (int l = 0; l < n; ++l){
if (l == j && k == i) continue;
if (slides[k].contain(points[l])){
addEdge(k, l + n);
}
}
}
if (bipartiteMatching() == n - 1){
sliding[i] = j;
}
}
}
}
out.println("Heap " + cnt);
StringBuilder sb = new StringBuilder();
boolean hasOne = false;
for (int i = 0; i < n; ++i){
if (sliding[i] >= 0){
char c = (char) ('A' + i);
sb.append("(" + c + "," + (sliding[i] + 1) + ")" + " ");
hasOne = true;
}
}
if (hasOne)
out.println(sb.toString().substring(0, sb.length() - 1));
else
out.println("none");
out.println();
}
}
//二分图匹配
List<Integer>[] g;
int[] matching;
public void init(int V){
g = new ArrayList[V];
for (int i = 0; i < V; ++i) g[i] = new ArrayList<Integer>();
matching = new int[V];
}
public void clear(){
for (int i = 0; i < V; ++i){
g[i].clear();
}
}
public void addEdge(int from, int to){
g[from].add(to);
g[to].add(from);
}
public boolean dfs(int v, boolean[] visited){
visited[v] = true;
for (int u : g[v]){
int w = matching[u];
if (w == -1 || !visited[w] && dfs(w, visited)){
matching[u] = v;
matching[v] = u;
return true;
}
}
return false;
}
public int bipartiteMatching(){
int cnt = 0;
Arrays.fill(matching, -1);
for (int i = 0; i < V; ++i){
if (matching[i] < 0){
if (dfs(i, new boolean[V])){
cnt ++;
}
}
}
return cnt;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017年07月23日，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录