校園自行車分配 II
KM算法
KM算法用來求二分圖最大權(quán)匹配牌借，或者二分圖最小權(quán)匹配度气。
即有兩個(gè)集合A和B，A中有元素m個(gè)膨报，B中有元素n個(gè)磷籍，且m<=n。A中每個(gè)元素和B中每個(gè)元素之間都有一個(gè)權(quán)重值现柠，現(xiàn)在問將A中每個(gè)元素都與B中一個(gè)元素進(jìn)行匹配院领，并且不能重復(fù)匹配B中的元素，問所有匹配的權(quán)值之和最大和最小是多少够吩？
如果用暴力遍歷的方法比然，比如回溯進(jìn)行計(jì)算，那么復(fù)雜度是：若n=m周循，則為强法。階乘的復(fù)雜度是極高的。
使用KM算法可以在復(fù)雜度內(nèi)解決最大權(quán)/最小權(quán)匹配問題湾笛。
KM算法的例子：
https://blog.csdn.net/qq_37943488/article/details/78586048
上面這個(gè)例子是二分最大全匹配的例子饮怯，即男女配對(duì)的例子，實(shí)現(xiàn)代碼如下：
public class KM {
private int[][] weight; // 二分圖兩邊頂點(diǎn)之間的權(quán)重:女生對(duì)每個(gè)男生的好感度
private int girlCount; // 女生數(shù)量
private int boyCount; // 男生數(shù)量
private int[] girlValues; // 女生的期望值
private int[] boyValues; // 男生的期望值
private int[] matched; // 記錄每個(gè)男生已經(jīng)匹配到的女生, -1代表尚未匹配到任何女生
private boolean[] girlVisit; // 記錄每一輪匹配過的女生
private boolean[] boyVisit; // 記錄每一輪匹配過的男生
private int[] lack; // 記錄每一輪的男生如果能被女生傾心至少還需要增加多少value
public KM(int[][] weight) throws Exception {
this.weight = weight;
init();
}
public void init() throws Exception {
girlCount = weight.length;
boyCount = weight[0].length;
if (girlCount > boyCount) {
throw new Exception("girlCount should less or equals than boyCount");
}
// 每個(gè)女生的期望值初始化為與她相連的男生的最大的好感度
girlValues = new int[girlCount];
for (int i = 0; i < girlCount; i++) {
girlValues[i] = weight[i][0];
for (int j = 1; j < boyCount; j++) {
girlValues[i] = Math.max(girlValues[i], weight[i][j]);
}
}
// 每個(gè)男生的期望值初始化為0
boyValues = new int[boyCount];
// 男生匹配到的女生初始化為-1, 代表男生都還沒每有匹配到女生
matched = new int[boyCount];
for (int i = 0; i < boyCount; i++) {
matched[i] = -1;
}
// 每一輪之前都需要初始化
girlVisit = new boolean[girlCount];
boyVisit = new boolean[boyCount];
lack = new int[boyCount];
}
// 為女生匹配對(duì)象, 成功返回true, 失敗返回false
public boolean dfs(int girl) {
girlVisit[girl] = true;
for (int boy = 0; boy < boyCount; boy++) {
if (boyVisit[boy]) {
continue;
}
int gap = girlValues[girl] + boyValues[boy] - weight[girl][boy];
if (gap == 0) {
boyVisit[boy] = true;
if (matched[boy] == -1 || dfs(matched[boy])) { // 找到一個(gè)沒有匹配的男生 或者該男生的妹子可以找到其他人
matched[boy] = girl;
return true;
}
} else {
lack[boy] = Math.min(lack[boy], gap);
}
}
return false;
}
public int getMaxMatchWeight() {
for (int girl = 0; girl < girlCount; girl++) {
initLack();
while (true) {
initBoyVisit();
initGirlVisit();
if (dfs(girl)) {
break; // 找到歸宿則退出
}
// 找不到歸宿, 則調(diào)整期望值:
// 所有訪問過的女生需要降低期望值, 降低多少取決于這一輪未被訪問的男生中最小的lack值
int down = Integer.MAX_VALUE;
for (int boy = 0; boy < boyCount; boy++) {
if (!boyVisit[boy]) {
down = Math.min(down, lack[boy]);
}
}
for (int theGirl = 0; theGirl < girlCount; theGirl++) {
if (girlVisit[theGirl]) {
girlValues[theGirl] -= down;
}
}
// 所有被訪問過的男生的期望值可以提升, 未被訪問過的男生的lack值可以減小
for (int theBoy = 0; theBoy < boyCount; theBoy++) {
if (boyVisit[theBoy]) {
boyValues[theBoy] += down;
} else {
lack[theBoy] -= down;
}
}
}
}
// 所有女生都匹配到男生, 返回匹配的weight之和即可
int totalWeight = 0;
for (int boy = 0; boy < boyCount; boy++) {
if (matched[boy] > -1) {
totalWeight += weight[matched[boy]][boy];
}
}
return totalWeight;
}
public void initGirlVisit() {
for (int i = 0; i < girlCount; i++) {
girlVisit[i] = false;
}
}
public void initBoyVisit() {
for (int i = 0; i < boyCount; i++) {
boyVisit[i] = false;
}
}
public void initLack() {
for (int i = 0; i < boyCount; i++) {
lack[i] = Integer.MAX_VALUE;
}
}
public static void main(String[] args) {
int[][] weight = {{3, 2, 3, 4}, {2, 2, 4, 6}, {0, 0, 3, 4}};
try {
KM km = new KM(weight);
int maxWeight = km.getMaxMatchWeight();
System.out.println(maxWeight);
} catch (Exception e) {
e.printStackTrace();
}
}
}
將上面的例子稍微更改嚎研，即可改為二分最小權(quán)的求解算法蓖墅，可應(yīng)用與本題的求解：
public class Solution {
public int assignBikes(int[][] workers, int[][] bikes) {
int m = workers.length;
int n = bikes.length;
int[][] weight = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
weight[i][j] = Math.abs(workers[i][0] - bikes[j][0]) + Math.abs(workers[i][1] - bikes[j][1]);
}
}
setWeight(weight);
return getMinMatchWeight();
}
private int[][] weight; // 二分圖兩邊頂點(diǎn)之間的權(quán)重:工人與自行車之間的曼哈頓距離
private int workerCount;
private int bikeCount;
private int[] workerValues;
private int[] bikeValues;
private int[] matched; // 記錄每輛自行車已經(jīng)匹配的工人
private boolean[] workerVisit; // 記錄每一輪匹配過的worker
private boolean[] bikeVisit; // 記錄每一輪匹配過的bike
private int[] lack; // 記錄每一輪的bike如果能被工人選中至少還需要減少多少距離
public void setWeight(int[][] weight) {
this.weight = weight;
init();
}
public void init() {
workerCount = weight.length;
bikeCount = weight[0].length;
// 每個(gè)worker的期望值初始化為與他距離最近的車的距離
workerValues = new int[workerCount];
for (int i = 0; i < workerCount; i++) {
workerValues[i] = weight[i][0];
for (int j = 1; j < bikeCount; j++) {
workerValues[i] = Math.min(workerValues[i], weight[i][j]); // 改動(dòng):期望值是最小距離
}
}
// 每個(gè)bike的期望值初始化為0
bikeValues = new int[bikeCount];
// bike匹配到的工人初始化為-1, 代表bike都還沒每有匹配到工人
matched = new int[bikeCount];
for (int i = 0; i < bikeCount; i++) {
matched[i] = -1;
}
// 每一輪之前都需要初始化
workerVisit = new boolean[workerCount];
bikeVisit = new boolean[bikeCount];
lack = new int[bikeCount];
}
// 為worker匹配自行車, 成功返回true, 失敗返回false
public boolean dfs(int worker) {
workerVisit[worker] = true;
for (int bike = 0; bike < bikeCount; bike++) {
if (bikeVisit[bike]) {
continue;
}
int gap = weight[worker][bike] - (workerValues[worker] + bikeValues[bike]); // 改動(dòng):保證gap為正數(shù)
if (gap == 0) {
bikeVisit[bike] = true;
if (matched[bike] == -1 || dfs(matched[bike])) { // 找到一個(gè)沒有匹配的bike 或者該bike的worker可以找到其他worker
matched[bike] = worker;
return true;
}
} else {
lack[bike] = Math.min(lack[bike], gap);
}
}
return false;
}
public int getMinMatchWeight() {
for (int worker = 0; worker < workerCount; worker++) {
initLack();
while (true) {
initBikeVisit();
initWorkerVisit();
if (dfs(worker)) {
break; // 找到biker則退出
}
// 找不到bike, 則調(diào)整距離:
// 所有訪問過的worker需要增加距離值, 增加多少取決于這一輪未被訪問的bike中最小的lack值
int down = Integer.MAX_VALUE;
for (int bike = 0; bike < bikeCount; bike++) {
if (!bikeVisit[bike]) {
down = Math.min(down, lack[bike]);
}
}
for (int theWorker = 0; theWorker < workerCount; theWorker++) {
if (workerVisit[theWorker]) {
workerValues[theWorker] += down; // 改動(dòng):降低期望值，即增大可容忍的距離
}
}
// 所有被訪問過的bike的距離值可以下降, 未被訪問過的bike的lack值可以減小
for (int theBoy = 0; theBoy < bikeCount; theBoy++) {
if (bikeVisit[theBoy]) {
bikeValues[theBoy] -= down; // 改動(dòng):增加bike的期望值嘉赎，即bike減小自身的值, 距離越近越容易被選擇
} else {
lack[theBoy] -= down;
}
}
}
}
// 所有worker都匹配到bike, 返回匹配的weight之和即可
int totalWeight = 0;
for (int bike = 0; bike < bikeCount; bike++) {
if (matched[bike] > -1) {
totalWeight += weight[matched[bike]][bike];
}
}
return totalWeight;
}
public void initWorkerVisit() {
for (int i = 0; i < workerCount; i++) {
workerVisit[i] = false;
}
}
public void initBikeVisit() {
for (int i = 0; i < bikeCount; i++) {
bikeVisit[i] = false;
}
}
public void initLack() {
for (int i = 0; i < bikeCount; i++) {
lack[i] = Integer.MAX_VALUE;
}
}
}
