?? 2195_goning home.cpp
字號:
#include <cstdio>
#include <cstring>
#include <iostream>
#include <memory.h>
#include <algorithm>
#include <math.h>
using namespace std;
#include"iostream"
#define INF (int)((unsigned int)(-1)>>1)
#define M 101
const int size = 101;
bool map[size][size]; // 二分圖的相等子圖, map[i][j] = true 代表Xi與Yj有邊
bool xckd[size], yckd[size]; // 標記在一次DFS中,Xi與Yi是否在交錯樹上
int match[size]; // 保存匹配信息,其中i為Y中的頂點標號,match[i]為X中頂點標號
int max(int a,int b)
{
return a>b?a:b;
}
int min(int a,int b)
{
return a<b?a:b;
}
bool DFS(int, const int);
bool KM_Perfect_Match(const int n, const int edge[][size])
{
int i, j;
int lx[size], ly[size]; // KM算法中Xi與Yi的頂標號
for(i = 0; i < n; i++) {
lx[i] = -INF;
ly[i] = 0;
for(j = 0; j < n; j++) {
lx[i] = max(lx[i], edge[i][j]);
}
}
bool perfect = false;
while(!perfect) {
// 初始化等式子圖
for(i = 0; i < n; i++) {
for(j = 0; j < n; j++) {
if(lx[i]+ly[j] == edge[i][j])
map[i][j] = true;
else map[i][j] = false;
}
}
// 匹配過程
int live = 0;
memset(match, -1, sizeof(match));
for(i = 0; i < n; i++) {
memset(xckd, false, sizeof(xckd));
memset(yckd, false, sizeof(yckd));
if(DFS(i, n)) live++;
else {
xckd[i] = true;
break;
}
}
if(live == n) perfect = true;
else {
// 修改標號過程
int ex = INF;
for(i = 0; i < n; i++) {
for(j = 0; xckd[i] && j < n; j++) { //xckd[i] == 1放在上層就錯了
if(!yckd[j]) ex = min(ex, lx[i]+ly[j]-edge[i][j]);
}
}
for(i = 0; i < n; i++) {
if(xckd[i]) lx[i] -= ex;
if(yckd[i]) ly[i] += ex;
}
}
}
return perfect;
}
// 此函數用來尋找是否有以Xp為起點的增廣路徑,返回值為是否含有增廣路
bool DFS(int p, const int n) //hangary算法
{
int i;
for(i = 0; i < n; i++) {
if(!yckd[i] && map[p][i]) {
yckd[i] = true;
int t = match[i];
match[i] = p; //有冗余
if(t == -1 || DFS(t, n)) {
return true;
}
match[i] = t;
if(t != -1) xckd[t] = true;
}
}
return false;
}
struct part
{
int i;
int j;
}man[M],house[M];
int main()
{
int n, m,edge[size][size]; // edge[i][j]為連接Xi與Yj的邊的權值
int i,j;int size0,size1;char c;
while(scanf("%d%d",&n,&m),n != 0&&m != 0)
{ size0 = 0;size1 = 0;
for(i = 0;i < n; i++)
{ scanf("\n");
for(j = 0;j < m; j++){
scanf("%c",&c);
if(c == 'm') { man[size0].i = i; man[size0++].j = j;}
if(c == 'H') {house[size1].i = i;house[size1++].j = j;}
}
}
for(i = 0;i < size0;i++){
for(j = 0;j < size1;j++){
edge[i][j] = -abs(man[i].i - house[j].i)-abs(man[i].j - house[j].j);
}
}
n = size0;
KM_Perfect_Match(n, edge);
int cost = 0;
for(i = 0; i < n; i++) cost += edge[match[i]][i];
printf("%d\n",-cost);
}
// cost 為最大匹配的總和, match[]中保存匹配信息
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -