UVA11383 二分图最佳完美匹配(模板程序)
程序员文章站
2022-06-09 20:17:29
...
分析:本题和最佳匹配没多大关系,但结果是KM算法的一个副产品。
KM算法跑一遍后,所有之和是最小的。
代码如下:
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn = 500+5;
const int INF = 1e9;
int W[maxn][maxn],n;
int Lx[maxn],Ly[maxn]; //顶标
int left[maxn]; //left[i]为右边第i个点的匹配点编号
bool S[maxn],T[maxn]; //S[i]和T[i]为左/右第i个点是否已标记
inline int MAX(int x, int y){return x>y?x:y;}
inline int MIN(int x, int y){return x<y?x:y;}
bool match(int i){
S[i] = 1;
for (int j=1; j<=n; j++) if (Lx[i]+Ly[j]==W[i][j] && !T[j]) {
T[j] = 1;
if (!left[j] || match(left[j])){
left[j] = i;
return 1;
}
}
return 0;
}
void update(){
int a = INF;
for (int i=1; i<=n; i++) if (S[i])
for (int j=1; j<=n; j++) if (!T[j])
a = MIN(a,Lx[i]+Ly[j]-W[i][j]);
for (int i=1; i<=n; i++) {
if (S[i]) Lx[i] -= a;
if (T[i]) Ly[i] += a;
}
}
void Print(){
int ans = 0;
for (int i=1; i<n; i++) {printf("%d ",Lx[i]); ans += Lx[i];} printf("%d\n",Lx[n]);
for (int i=1; i<n; i++) {printf("%d ",Ly[i]); ans += Ly[i];} printf("%d\n",Ly[n]);
printf("%d\n",ans+Lx[n]+Ly[n]);
}
void KM(){
for (int i=1; i<=n; i++) {
left[i] = Lx[i] = Ly[i] = 0;
for (int j=1; j<=n; j++) Lx[i] = MAX(Lx[i],W[i][j]);
}
for (int i=1; i<=n; i++){
for (;;){
for (int j=1; j<=n; j++) S[j] = T[j] = 0;
if (match(i)) break; else update();
}
}
}
void init(){
for (int i=1; i<=n; i++) {
for (int j=1; j<=n; j++) scanf("%d",&W[i][j]);
}
KM();
}
int main(){
while (scanf("%d",&n)!=EOF){
init();
Print();
}
return 0;
}
上一篇: Java 绘制图标(饼状图)JFreeChart快速通过Java创建图表
下一篇: 二分图匹配