HDU 1533 & KM模板

题意

  求二分图最小完备匹配。

SOL

  建个图那么方便的事情是吧。。。然后边权都是正的(好像根边权也没什么关系),既然要求最小那么把边权取个相反数跑个KM就好了。。

CODE:

/*==========================================================================
# Last modified: 2016-02-16 19:55
# Filename: hdu1533.cpp
# Description:
==========================================================================*/
#define me AcrossTheSky
#include <cstdio>
#include <cmath>
#include <ctime>
#include <string>
CODE:
#include <cstring>
#include <cstdlib>
#include <iostream>
#include <algorithm> #include <set>
#include <map>
#include <stack>
#include <queue>
#include <vector>
#define lowbit(x) (x)&(-x)
#define INF 1070000000
#define FOR(i,a,b) for((i)=(a);(i)<=(b);(i)++)
#define FORP(i,a,b) for(int i=(a);i<=(b);i++)
#define FORM(i,a,b) for(int i=(a);i>=(b);i--)
#define ls(a,b) (((a)+(b)) << 1)
#define rs(a,b) (((a)+(b)) >> 1)
#define maxn 200
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
/*==================split line==================*/ int n,sumx,sumy;
int w[maxn][maxn],link[maxn],lx[maxn],ly[maxn],slack[maxn],x[maxn],y[maxn];
bool S[maxn],T[maxn];
int calc(int i,int j){
int y1=x[i]%1000,x1=x[i]/1000,y2=y[j]%1000,x2=y[j]/1000;
return -(abs(y1-y2)+abs(x1-x2));
}
void build_graph(){
FORP(i,1,n)
FORP(j,1,n)
w[i][j]=calc(i,j);
}
bool match(int i){
S[i]=true;
FORP(j,1,n){
if (T[j]) continue;
int tmp=lx[i]+ly[j]-w[i][j];
if (tmp==0){
T[j]=true;
if (!link[j] || match(link[j])){
link[j]=i;
return true;
}
}
else slack[j]=min(slack[j],tmp);
}
return false;
}
void updata(){
int a=INF;
FORP(i,1,n) if (!T[i]) a=min(a,slack[i]);
FORP(i,1,n) {
if (S[i]) lx[i]-=a;
if (T[i]) ly[i]+=a;
else slack[i]-=a;
}
}
int KM(){ memset(link,0,sizeof(link));
memset(ly,0,sizeof(ly));
FORP(i,1,n)
FORP(j,1,n) lx[i]=max(lx[i],w[i][j]); FORP(i,1,n){
memset(slack,0x7f,sizeof(slack));
while (1){
memset(S,false,sizeof(S));
memset(T,false,sizeof(T));
if (match(i)) break;
else updata();
}
}
int ans=0;
FORP(i,1,n) if (link[i])
ans+=w[link[i]][i];
return -ans;
}
int main(){
//freopen("a.in","r",stdin);
int r,c;
while (1){
sumx=0; sumy=0;
scanf("%d%d",&r,&c);
if (r==0 && c==0) return 0;
FORP(i,1,r){
char ch[1000];
scanf("%s",ch);
FORP(j,0,c-1)
if (ch[j]=='m') x[++sumx]=i*1000+j+1;
else if (ch[j]=='H') y[++sumy]=i*1000+j+1;
}
n=sumx;
build_graph();
printf("%d\n",KM());
}
}
上一篇:[转载]centos下yum安装samba及配置


下一篇:在Centos中yum安装和卸载软件的使用方法(转)