Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
哪位大牛看一下我这哪错了#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int size = 160; const int INF = 100000000; // 相对无穷大 bool map[size][size]; // 二分图的相等子图, map[i][j] = true 代表Xi与Yj有边 bool xckd[size], yckd[size]; // 标记在一次DFS中,Xi与Yi是否在交错树上 int match[size]; // 保存匹配信息,其中i为Y中的顶点标号,match[i]为X中顶点标号 int abs(int x) { if(x<0) return -x; return x; } bool DFS(int, const int); int min(int a,int b) { if(a<b) return a; return b; } int max(int a,int b) { if(a>b) return a; return b; } void KM_Perfect_Match(const int n, const int edge[][size]) { int i, j; int lx[size], ly[size]; // KM算法中Xi与Yi的标号 for(i = 0; i < n; i++) { lx[i] = INF; ly[i] = 0; for(j = 0; j < n; j++) { lx[i] = min(lx[i], edge[i][j]); } } bool perfect = false; while(!perfect) { // 初始化邻接矩阵 for(i = 0; i < n; i++) { for(j = 0; j < n; j++) { if(lx[i]+ly[j] == edge[i][j]) map[i][j] = true; else map[i][j] = false; } } // 匹配过程 int live = 0; memset(match, -1, sizeof(match)); for(i = 0; i < n; i++) { memset(xckd, false, sizeof(xckd)); memset(yckd, false, sizeof(yckd)); if(DFS(i, n)) live++; else { xckd[i] = true; break; } } if(live == n) perfect = true; else { // 修改标号过程 int ex = INF; for(i = 0; i < n; i++) { for(j = 0; xckd[i] && j < n; j++) { if(!yckd[j]) ex = min(ex, lx[i]+ly[j]-edge[i][j]); } } for(i = 0; i < n; i++) { if(xckd[i]) lx[i] -= ex; if(yckd[i]) ly[i] += ex; } } } } // 此函数用来寻找是否有以Xp为起点的增广路径,返回值为是否含有增广路 bool DFS(int p, const int n) { int i; for(i = 0; i < n; i++) { if(!yckd[i] && map[p][i]) { yckd[i] = true; int t = match[i]; match[i] = p; if(t == -1 || DFS(t, n)) { return true; } match[i] = t; if(t != -1) xckd[t] = true; } } return false; } int main() { int n, edge[size][size],a,b,c; // edge[i][j]为连接Xi与Yj的边的权值 int i,man[105][2],house[105][2],j; char s[105]; while(scanf("%d%d",&a,&b)!=EOF&&a&&b) { c=n=0; for(i=0;i<a;i++) { scanf("%s",s); for(j=0;s[j]!='\0';j++) { if(s[j]=='m') { man[n][0]=i; man[n++][1]=j; } if(s[j]=='H') { house[c][0]=i; house[c++][1]=j; } } } for(i=0;i<n;i++) { for(j=0;j<n;j++) { edge[i][j]=abs(man[i][0]-house[j][0])+abs(man[i][1]-house[j][1]); } } KM_Perfect_Match(n, edge); int cost = 0; for(i = 0; i < n; i++) cost += edge[match[i]][i]; printf("%d\n",cost); } // cost 为最大匹配的总和, match[]中保存匹配信息 return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator