/*
wywcgs 的KM O(n^3)
只需要把Graph里的n(顶点数)和edge[x][y](边权)赋值，第一维为x点，第二维为y点。
然后调用KMMatch()函数即可，返回值为最大权完美匹配。
最小权匹配可将每条边权取反，然后类似求最大权匹配即可。
匹配信息保存在xmate[]和ymate[]中。其中xmate[i]为x[i]的匹配点，ymate[i]为y[i]的匹
配点。
*/
#include <cstdio>
#include <queue>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 310;
const int INF = 1 << 28;
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::bfs()
{
while(!Q.empty())
{
int p = Q.front(), u = p>>1; Q.pop();
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));
for(int i = 0; i < n; i++)
{
lx[i] = -INF;
for(int j = 0; j < n; j++) lx[i] >?= edge[i][j];
}
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(int 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(int i = 0; i < n; i++)
if(!yckd[i]) ex <?= slack[i];
for(int i = 0; i < n; i++) {
if(xckd[i]) lx[i] -= ex;
if(yckd[i]) ly[i] += ex;
slack[i] -= ex;
}
for(int i = 0; i < n; i++)
if(!yckd[i] && slack[i] == 0) { yckd[i] = true; Q.push((i<<1)|1); }
}
int cost = 0;
for(int i = 0; i < n; i++) cost += edge[i][xmate[i]];
return cost;
}
bool Graph::make()
{
int i, j;
while (scanf("%d", &n) == 1)
{
for (i = 0; i < n; i++)
for (j = 0; j < n; j++)
scanf("%d", &edge[i][j]);
return true;
}
return false;
}
int main()
{
Graph g;
while(g.make()) printf("%d\n", g.KMMatch());
return 0;
}
5 个解决方案
#1
由于本人对这个算法还不太熟悉，所以猜不出这两个代码的意思。。。
#2
这个根本不是正确的C++的语法，编译不能通过。请问你用的什么编译器？C++没有这样的操作符。
#3
gcc的扩展，a<?b表示a<b?a:b，a<?=b表示a=a<?b
然后最新版的gcc自己都丢弃了这种语法。
然后最新版的gcc自己都丢弃了这种语法。
#4
加一分嫌多，减一分嫌少。
#5
非常感谢
#1
由于本人对这个算法还不太熟悉，所以猜不出这两个代码的意思。。。
#2
这个根本不是正确的C++的语法，编译不能通过。请问你用的什么编译器？C++没有这样的操作符。
#3
gcc的扩展，a<?b表示a<b?a:b，a<?=b表示a=a<?b
然后最新版的gcc自己都丢弃了这种语法。
然后最新版的gcc自己都丢弃了这种语法。
#4
加一分嫌多，减一分嫌少。
#5
非常感谢