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 20060820302 at 2009-01-22 20:58:13
#include<iostream>
using namespace std;
struct point 
{
     int x,y;       
};
point p1[1005],p2[1005];
const int N=1005;
const int inf=999999;
int x[N],y[N];
int mx[N],my[N];
int map[N][N];
int lx[N],ly[N];
int slack[N];
int n;
bool dfs(int v)
{
   int j;
   x[v]=1;
   for(j=0;j<n;j++)
   {
      int wt=lx[v]+ly[j]-map[v][j];
      if(!y[j]&& wt==0)
      {
          y[j]=1;
          if(my[j]== -1||dfs(my[j]))
          {
              my[j]=v;//mx[v]=j;
              return true;
                                    
          }                
      }  
      else if(slack[j]>-wt) slack[j]=-wt;
   }
   return false;
 }

int  perfect_match(int n)
{
   int i,j,k;
   for(i=0;i<n;i++)
     {
          my[i]=-1;
         lx[i]=inf;ly[i]=0;
         for(j=0;j<n;j++)
         {
           if(lx[i]>map[i][j])  lx[i]=map[i][j];                
         }            
     }    
    for(k=0;k<n;k++)
    {
        for(i=0;i<n;i++) x[i]=0,y[i]=0,slack[i]=inf;        
         while(!dfs(k))
         {
             int ans;
             //printf("ans=%d\n",ans);
             int d=inf;
             for(i=0;i<n;i++)
             {
               if(!y[i]&&slack[i]<d)  d=slack[i];                
             }                
             for(i=0;i<n;i++)
             {
                if(x[i])  {lx[i]+=d;}
                if(y[i])  {ly[i]-=d;}                             
                else slack[i]-=d;            
             }          
                
         }                
                    
    }
    int  ans=0;   
    for(i=0;i<n;i++)
        ans+=lx[i]+ly[i];  
    return ans;
}
int main()
{
      int m;
      int i,j,k,l;
      char a;
      while(scanf("%d%d",&n,&m)!=EOF)
      {
          k=0;l=0;
          if(n==0 && m==0) break;
         
          for(i=0;i<n;i++)
         {
            getchar();
            for(j=0;j<m;j++)
            {
                 scanf("%c",&a);  
                 if(a=='m')
                 p1[l].x=i,p1[l++].y=j;
                 if(a=='H')
                 p2[k].x=i,p2[k++].y=j;
            }
         }      
        for(i=0;i<=l;i++)
           for(j=0;j<=k;j++)
           {
               map[i][j]=(abs(p1[i].x-p2[j].x)+abs(p1[i].y-p2[j].y));                
           }                                        
         printf("%d\n",perfect_match(l));                            
                                     
      }    
     // system("pause");
    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