//题目类型：二分匹配-最小权完美匹配//算法实现：可以采用KM算法或者最小费用最大流实现//KM算法实现 #include <iostream>#include <string>#include <math.h>//#include <conio.h>using namespace std;#define arraysize 105int maxData = 1000000000; int w[arraysize][arraysize];int match[arraysize];int lx[arraysize],ly[arraysize],slack[arraysize];bool finalx[arraysize],finaly[arraysize];int hcount,mcount; //由题目可知，hcount=mcount,所以直接使用KM算法进行最大权完美匹配 typedef struct house{ int row; int col;}house;typedef struct littleman{ int row; int col;}littleman;littleman mans[arraysize];house houses[arraysize];bool DFS(int p){ int i,j,t; finalx[p] = true; for(i=1;i<=hcount;++i) { if(finaly[i]) continue; int temp = lx[p]+ly[i]-w[p][i]; if(temp==0) { finaly[i] = true; t = match[i]; match[i] = p; if(t==0 || DFS(t)) return true; match[i] = t; } else if(slack[i]>temp) { slack[i] = temp; } } return false;}int KM(){ int i,j; memset(ly,0,sizeof(ly)); memset(match,0,sizeof(match)); for(i=1;i<=mcount;++i) { lx[i]=-maxData; for(j=1;j<=hcount;++j) { if(lx[i]<w[i][j]) lx[i] = w[i][j]; } } for(i=1;i<=mcount;++i) { for(j=1;j<=hcount;++j) slack[j] = maxData; while(1) { memset(finalx,0,sizeof(finalx)); memset(finaly,0,sizeof(finaly)); if(DFS(i)) break; int d = maxData; for(j=1;j<=hcount;++j) { if(!finaly[j] && d>slack[j]) d = slack[j]; } for(j=1;j<=mcount;++j) { if(finalx[j]) lx[j]-= d; if(finaly[j]) ly[j]+= d; else slack[j] -= d; } } } int ans= 0; for(i=1;i<=mcount;++i) { ans -=(lx[i]+ly[i]); //结果加的权值需要取反 } return ans;}int main(){ //freopen("1.txt","r",stdin); int i,j; int n,m; string tempstr; while(cin>>n>>m) { if(n==0 && m==0) break; hcount = 0; mcount = 0; for(i=1;i<=n;++i) { cin>>tempstr; for(j=0;j<tempstr.size();++j) { if(tempstr[j]=='H') { hcount++; houses[hcount].row = i; houses[hcount].col = j+1; } else if(tempstr[j]=='m') { mcount++; mans[mcount].row = i; mans[mcount].col = j+1; } } } for(i=1;i<=mcount;++i) { for(j=1;j<=hcount;++j) { //KM算法求的是最大权的完美匹配，所以将权值取反,权值是距离 w[i][j] = -(abs(mans[i].row-houses[j].row)+abs(mans[i].col-houses[j].col)); } } cout<<KM()<<endl; } //getch(); return 0;}
//使用最小费用最大流实现 //本题的关键在于建图：将小人和房间都作为图中的点，并设置一超级源点和超级终点，小人和房间的容量设置为1，费用设置为距离。源点到小人//的容量设置为1，费用为0；房间到终点的容量设置为1，费用设置为0 #include <iostream>#include <string>//#include <conio.h>#include <queue>#include <math.h>using namespace std;#define arraysize 205typedef struct house{ int row; int col;}house;typedef struct littleman{ int row; int col;}littleman;house houses[101];littleman mans[101];int n,m; int mcount,hcount;int maxData = 10000000;int capacity[arraysize][arraysize];int kcost[arraysize][arraysize];bool final[arraysize]; //SPFA算法中标识结点是否在队列中 int d[arraysize];int flow[arraysize][arraysize];int pre[arraysize];int ncount;
void SPFA(int src){ queue<int> myqueue; int i,j; memset(final,0,sizeof(final)); memset(pre,-1,sizeof(pre)); myqueue.push(src); for(i=0;i<=ncount;++i) //SPFA算法与Dij不同，SPFA初始化时将除源点以外所有点的最短距离初始化无穷大,ncount为结点总数 { d[i] = maxData; } d[src] = 0; //源点最短距离设置成0 final[src] = true; while(!myqueue.empty()) //SPFA算法可入队列多次 { int frontint = myqueue.front();myqueue.pop(); final[frontint] = false; for(i=0;i<=ncount;++i) { if(capacity[frontint][i]>flow[frontint][i] && d[i]>d[frontint]+kcost[frontint][i]) //c[u][v]>f[u][v]说明<u,v>之间流量可以进行增加 { d[i] = d[frontint]+kcost[frontint][i]; pre[i] = frontint; //修改前驱 if(!final[i]) { final[i] = true; myqueue.push(i); } } } }}void minCost(int src,int des){ int minAdd = maxData; int p; while(1) { SPFA(src); if(pre[des]==-1) //表示已无增广路 break; minAdd = maxData; p = des; while(pre[p]!=-1) { minAdd = min(minAdd,(capacity[pre[p]][p]-flow[pre[p]][p])); //求的增广路的可增流量 p = pre[p]; } p = des; while(pre[p]!=-1) //沿着最小费用路进行增广 { flow[pre[p]][p] += minAdd; flow[p][pre[p]] -= minAdd; p = pre[p]; } } }int main(){ //freopen("1.txt","r",stdin); int i,j; int src,des; int flowcost; string tempstr; while(cin>>n>>m) { if(n==0 && m==0) break; flowcost = 0; //最小费用 mcount = 0; //小人的数目 hcount = 0; //房间的数目 memset(kcost,0,sizeof(kcost)); memset(capacity,0,sizeof(capacity)); memset(flow,0,sizeof(flow)); for(i=1;i<=n;++i) { cin>>tempstr; for(j=0;j<tempstr.size();++j) { if(tempstr[j]=='H') { hcount++; houses[hcount].row = i; houses[hcount].col = j+1; } else if(tempstr[j]=='m') { mcount++; mans[mcount].row = i; mans[mcount].col = j+1; } } } //小人和房间之间构图 for(i=1;i<=mcount;++i) { for(j=1;j<=hcount;++j) { kcost[i][j+mcount] = abs(mans[i].row-houses[j].row)+abs(mans[i].col-houses[j].col); //费用设置为距离 kcost[j+mcount][i] = -kcost[i][j+mcount]; capacity[i][j+mcount] = 1; } } src = 0; des = hcount+mcount+1; ncount = hcount+mcount+2; //结点总数 //源点到小人之间构图 for(i=1;i<=mcount;++i) { capacity[src][i] = 1; } //房间到终点之间构图 for(j=1;j<=hcount;++j) { capacity[j+mcount][des] = 1; } minCost(src,des); for(i=1;i<=mcount;++i) { for(j=1;j<=hcount;++j) { flowcost += kcost[i][j+mcount]*flow[i][j+mcount]; //最小费用 } } cout<<flowcost<<endl; } //getch(); return 0;}
转载于:https://www.cnblogs.com/north_dragon/archive/2010/06/03/1750812.html
相关资源：数据结构—成绩单生成器