学步园

POJ 2195

http://acm.pku.edu.cn/JudgeOnline/problem?id=2195

第一道二分图最佳匹配题，简单题，会二分最佳的这题也就会。就建图的时候要把距离算出来！

#include <iostream><br /> #include <cmath><br /> using namespace std;</p> <p>int n,m;<br /> int num1,num2;<br /> char map[150][150]; //初始输入<br /> int mat[150][150]; //记录距离<br /> int house[150][2]; //房子坐标<br /> int man[150][2]; //人的坐标<br /> int pl[150],pr[150]; //左右顶标<br /> int visl[150],visr[150]; //是否被访问<br /> int match[150]; //匹配<br /> int stack[150];</p> <p>int Min(int a,int b)<br /> {<br /> return a>b?b:a;<br /> }</p> <p>bool find(int a) // 找增广路径<br /> {<br /> int i;<br /> visl[a] = 1;<br /> for(i=0;i<num2;i++)<br /> {<br /> if(visr[i] == 0)<br /> {<br /> int val = pl[a] + pr[i] - mat[a][i];<br /> if(val == 0)<br /> {<br /> visr[i] = 1;<br /> if(match[i] == -1 || find(match[i]))<br /> {<br /> match[i] = a;<br /> return 1;<br /> }<br /> }<br /> else<br /> {<br /> if(val < stack[i])<br /> stack[i] = val;<br /> }<br /> }<br /> }</p> <p> return 0;<br /> }</p> <p>int km()<br /> {<br /> int i,j,k;<br /> //初始化顶标<br /> for(i=0;i<num1;i++)<br /> {<br /> pl[i] = -0x7ffffff;<br /> pr[i] = 0;<br /> for(j=0;j<num2;j++)<br /> {<br /> if(mat[i][j] > pl[i])<br /> pl[i] = mat[i][j];<br /> }<br /> }</p> <p> memset(match,-1,sizeof(match));<br /> for(k=0;k<num1;k++)<br /> {<br /> for(i=0;i<150;i++)<br /> stack[i] = 0x7fffffff;</p> <p> while(1)<br /> {<br /> memset(visl,0,sizeof(visl));<br /> memset(visr,0,sizeof(visr));<br /> if(find(k))<br /> break;</p> <p> int d = 0x7ffffff;<br /> for(j=0;j<num2;j++)<br /> {<br /> if(!visr[j])<br /> d = Min(stack[j] , d);<br /> }</p> <p> for(i=0;i<num1;i++)<br /> {<br /> if(visl[i])<br /> pl[i] -= d;<br /> if(visr[i])<br /> pr[i] += d;<br /> }<br /> }<br /> }</p> <p> int sum = 0;<br /> for(i=0;i<num1;i++)<br /> {<br /> sum += -1 * mat[match[i]][i];<br /> }</p> <p> return sum;<br /> }<br /> void Init()<br /> {<br /> int i,j;<br /> num1 = 0; //房子个数<br /> num2 = 0; //人的个数<br /> for(i=0;i<n;i++)<br /> {<br /> cin>>map[i];<br /> for(j=0;j<m;j++)<br /> {<br /> if(map[i][j] == 'H')<br /> {<br /> house[num1][0] = i;<br /> house[num1++][1] = j;<br /> }<br /> if(map[i][j] == 'm')<br /> {<br /> man[num2][0] = i;<br /> man[num2++][1] = j;<br /> }<br /> }<br /> }<br /> for(i=0;i<num1;i++)<br /> {<br /> for(j=0;j<num2;j++)<br /> {<br /> mat[i][j] = abs(house[i][0] - man[j][0]) + abs(house[i][1] - man[j][1]);<br /> mat[i][j] = - mat[i][j]; //因为是取最小权值，所以取反<br /> }<br /> }<br /> }</p> <p>int main()<br /> {<br /> while(scanf("%d%d",&n,&m)!=EOF && (n!=0 || m!=0))<br /> {<br /> Init();<br /> printf("%d/n",km());<br /> }<br /> return 0;<br /> }</p> <p>