本文主要是介绍poj 2516 Minimum Cost KM算法 最小权值匹配，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一开始想到了就是拆点，题目说每个人对每种goods的需求都是只有0-3，我是从这个想到的。。。
接下来就是建立模型拉。然后就是KM算法。。
#include<iostream>
#include<cstdio>#include<cstring>
#include<algorithm>
using namespace std;
int shop[51][51];
int store[51][51];
int cost[51][51][51];
int sum1[51];
int sum2[51];
int max(int x,int y){
if(x>y)return x;
return y;
}
int min(int x,int y){
if(x>y)return y;
return x;
}
char maze[200][200];/根据题目要求建二分图的需要
int weight[200][200];///二分图中各个顶点的标号
int match[200];匹配结果
int lx[200],ly[200];记录顶点的标号
int lack;当无法增广路时应该缩小的范围
int visx[200],visy[200];//记录此次的匹配访问过的结点
int num;/记录总共有多少个顶点
int num2;
bool dfs(int u){/找增广路，其实和最大匹配差不多
visx[u] = 1;
for(int v = 1;v<num2;++v){
if(!visy[v]){
int t = lx[u]+ly[v]-weight[u][v];
if(t==0){
visy[v] = true;
if(match[v]==-1 ||dfs(match[v]))
{
match[v] = u;
return true;
}
}
else lack = max(lack,t);///靠这个记录该缩小的范围
}
}
return false;
}
long long KM()
{
int i,j;
for(i =1;i<num;i++){///初始化
lx[i] = 100000000;
for(j = 1;j<num2;j++)lx[i] = min(lx[i],weight[i][j]);
}
for(int i = 1;i<num2;i++)ly[i] = 0;
memset(match,-1,sizeof(match));
for(int u = 1;u<num;u++)
while(1){
memset(visx,false,sizeof(visx));
memset(visy,false,sizeof(visy));
lack = -10000000;
if(dfs(u))break;
这篇关于poj 2516 Minimum Cost KM算法 最小权值匹配的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
