?? 2195(3).cpp
字號:
#include <cstdio>
#include <queue>
#include <algorithm>
using namespace std; //O(N^3)
const int N = 128;
#define INF (int)((unsigned int)(-1)>>1)
class Graph {
private:
bool xckd[N], yckd[N];
int n, edge[N][N], xmate[N], ymate[N];
int lx[N], ly[N], slack[N], prev[N];
queue<int> Q;
bool bfs();
void agument(int);
public:
bool make();
int KMMatch();
};
bool Graph::make() {
int house[N], child[N], h, w, cn = 0; int i,j;
char line[N];
scanf("%d %d", &h, &w);
if(w == 0) return false;
scanf("\n"); n = 0;
for( i = 0; i < h; i++) {
gets(line);
for(int j = 0; line[j] != 0; j++) {
if(line[j] == 'H') house[n++] = i * N + j;
if(line[j] == 'm') child[cn++] = i * N + j;
}
}
for( i = 0; i < n; i++) {
int cr = child[i] / N, cc = child[i] % N;
for( j = 0; j < n; j++) {
int hr = house[j] / N, hc = house[j] % N;
edge[i][j] = -abs(cr-hr) - abs(cc-hc);
}
}
return true;
}
bool Graph::bfs() { //移位操作 用到狀態壓縮思想
while(!Q.empty()) {
int p = Q.front(), u = p>>1; Q.pop(); //隊列元素末位1用于辨別元素為y方
if(p&1) {
if(ymate[u] == -1) { agument(u); return true; }
else { xckd[ymate[u]] = true; Q.push(ymate[u]<<1); }
}
else {
for(int i = 0; i < n; i++)
if(yckd[i]) continue;
else
if(lx[u]+ly[i] != edge[u][i]) {
int ex = lx[u]+ly[i]-edge[u][i];
if(slack[i] > ex) { slack[i] = ex; prev[i] = u; }
}
else {
yckd[i] = true; prev[i] = u;
Q.push((i<<1)|1);
}
}
}
return false;
}
void Graph::agument(int u) { //構造交錯樹
while(u != -1) {
int pv = xmate[prev[u]];
ymate[u] = prev[u];
xmate[prev[u]] = u;
u = pv;
}
}
int Graph::KMMatch() {
memset(ly, 0, sizeof(ly)); int i,j;
for( i = 0; i < n; i++) {
lx[i] = -INF;
for( j = 0; j < n; j++) lx[i] = lx[i] < edge[i][j]?edge[i][j]:lx[i];
}
memset(xmate, -1, sizeof(xmate)); memset(ymate, -1, sizeof(ymate));
bool agu = true;
for(int mn = 0; mn < n; mn++) {
if(agu) {
memset(xckd, false, sizeof(xckd));
memset(yckd, false, sizeof(yckd));
for( i = 0; i < n; i++) slack[i] = INF;
while(!Q.empty()) Q.pop();
xckd[mn] = true; Q.push(mn<<1);
}
if(bfs()) { agu = true; continue; }
int ex = INF; mn--; agu = false;
for( i = 0; i < n; i++)
if(!yckd[i]) ex = ex > slack[i]?slack[i]:ex;//ex <?= slack[i];
for( i = 0; i < n; i++) {
if(xckd[i]) lx[i] -= ex;
if(yckd[i]) ly[i] += ex;
slack[i] -= ex; //同步更新slack[y]
}
for( i = 0; i < n; i++)
if(!yckd[i] && slack[i] == 0) { yckd[i] = true; Q.push((i<<1)|1); }
}
int cost = 0;
for( i = 0; i < n; i++) cost += edge[i][xmate[i]];
return cost;
}
int main()
{
Graph g;
while(g.make()) printf("%d\n", -g.KMMatch());
return 0;
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -