是为了学习KM算法敲这道题的,虽然是模版题,但是还是看着解题报告才敲出来的,KM还是有点深奥,有些地方没看懂,原理也是似懂非懂.........
先放一放 等以后再细细揣摩
code
#include <set>
#include <map>
#include <ctime>
#include <queue>
#include <cmath>
#include <stack>
#include <limits>
#include <vector>
#include <bitset>
#include <string>
#include <cstdio>
#include <cstring>
#include <fstream>
#include <string.h>
#include <iostream>
#include <algorithm>
#define Si set<int>
#define LL long long
#define pb push_back
#define PS printf(" ")
#define Vi vector<int>
#define LN printf("\n")
#define lson l,m,rt << 1
#define rson m+1,r,rt<<1|1
#define SD(a) scanf("%d",&a)
#define PD(a) printf("%d",a)
#define SET(a,b) memset(a,b,sizeof(a))
#define FF(i,a) for(int i(0);i<(a);i++)
#define FD(i,a) for(int i(a);i>=(1);i--)
#define FOR(i,a,b) for(int i(a);i<=(b);i++)
#define FOD(i,a,b) for(int i(a);i>=(b);i--)
#define readf freopen("input.txt","r",stdin)
#define writef freopen("output.txt","w",stdout)
const int maxn = 102;
const int INF = 0x3fffffff;
const int dx[]={0,1,0,-1};
const int dy[]={1,0,-1,0};
const double pi = acos(-1.0);
const double eps= 1e-7;
using namespace std;
int N,M,nx,ny;
int w[maxn][maxn];
int men[maxn][2],home[maxn][2];
int lx[maxn],ly[maxn];
bool visx[maxn],visy[maxn];
int link[maxn],slack[maxn];
bool find(int x){
visx[x]=true;
FOR(y,1,ny){
if(visy[y]) continue;
int t=lx[x]+ly[y]-w[x][y];
if(t==0){
visy[y]=true;
if(link[y]==0||find(link[y])){
link[y]=x;
return true;
}
}else{
slack[y]=min(slack[y],t);
}
}
return false;
}
int KM(){
SET(link,0);SET(ly,0);
FOR(x,1,nx){
lx[x]=-INF;
FOR(y,1,ny){
if(w[x][y]>lx[x]) lx[x]=w[x][y];
}
}
FOR(x,1,nx){
FOR(y,1,ny){
slack[y]=INF;
}
while(true){
SET(visx,0);SET(visy,0);
if(find(x)) break;
int d=INF;
FOR(i,1,ny){
if(!visy[i] && d>slack[i])
d=slack[i];
}
FOR(i,1,nx){
if(visx[i]) lx[i]-=d;
}
FOR(i,1,ny){
if(visy[i]) ly[i]+=d;
else slack[i]-=d;
}
}
}
int ans=0;
FOR(i,1,ny){
ans+=w[link[i]][i];
}
return -ans;
}
int main()
{
char ch;
while(~scanf("%d%d",&N,&M)&&(N+M)){
nx=ny=0;
FOR(i,1,N) FOR(j,1,M){
scanf(" %c",&ch);
if(ch=='m'){
men[++nx][0]=i;
men[nx][1]=j;
}
if(ch=='H'){
home[++ny][0]=i;
home[ny][1]=j;
}
}
FOR(i,1,nx) FOR(j,1,ny){
w[i][j]=-(abs(men[i][0]-home[j][0])+abs(men[i][1]-home[j][1]));
}
PD(KM());LN;
}
return 0;
}
分享到:
相关推荐
北大POJ2195-Going Home【费用流】 解题报告+AC代码 http://blog.csdn.net/lyy289065406/article/details/6732762
这是北京大学ACM也就是POJ2195的源代码,用的是最优匹配算法。
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
* 最小费用最大流:例如 poj2516、poj2516、poj2195。 * 双连通分量:例如 poj2942。 * 强连通分支及其缩点:例如 poj2186。 * 图的割边和割点:例如 poj3352。 * 最小割模型、网络流规约:例如 poj3308。 3. ...
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj 百练 题目分类 poj 百练 题目分类
POJ1083的代码,POJ1083的代码,POJ1083的代码
POJ1048,加强版的约瑟夫问题 难度中等
北大POJ2002-Squares 解题报告+AC代码
poj 1001答案
POJ2968代码有用,欢迎下载,POJ代码