Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

哪位大牛看一下我这哪错了

Posted by yygy at 2009-02-27 15:59:04 on Problem 2195
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator