匹配算法

/*
 * Title          : Matching Algorithm
 * Created by     : Fennec
 * Date           : Monday, Oct 01, 2004
 * Time           :
 * Method         :
 * Other          :
 *
 */

#include <stdio.h>
#include <string.h>
const int MaxLeftsize=105;
const int MaxRightsize=305;
int Edge_lsize[MaxLeftsize+2];
int Edge_rsize[MaxRightsize+2];

int Edge_left[MaxLeftsize+2][MaxRightsize+2];
int Edge_right[MaxRightsize+2][MaxLeftsize+2];

int Ptr_l[MaxLeftsize+2];
int Ptr_r[MaxRightsize+2];

int Visited_l[MaxLeftsize+2];
int Visited_r[MaxRightsize+2];

int Father_l[MaxLeftsize+2];
int Father_r[MaxLeftsize+2];
int L_size,R_size;
int flag;
int main()
{
// freopen("input.txt","r",stdin);
// freopen("o.txt","w",stdout);
 int kase;
 int i,j;
 int t;
 int tf;
 scanf("%d",&kase);
 while(kase--){
  //input
  scanf("%d%d",&L_size,&R_size);
  memset(Edge_rsize,0,sizeof(Edge_rsize));
  memset(Ptr_l,-1,sizeof(Ptr_l));
  memset(Ptr_r,-1,sizeof(Ptr_r));
  for(i=0;i<L_size;++i){
   scanf("%d",&Edge_lsize[i]);  
   for(j=0;j<Edge_lsize[i];++j){
    scanf("%d",&Edge_left[i][j]);
    --Edge_left[i][j];
    Edge_right[Edge_left[i][j]][Edge_rsize[Edge_left[i][j]]]=i;
    ++Edge_rsize[Edge_left[i][j]];
   }
  }

  //cupidity
  for(i=0;i<L_size;++i){
   for(j=0;j<Edge_lsize[i];++j){
    if(Ptr_r[ Edge_left[i][j] ]==-1){
     Ptr_l[i]=Edge_left[i][j];
     Ptr_r[Edge_left[i][j]]=i;
     break;
    }
   }
  }

  //find ope 
  while(true){
   //pre ope
   memset(Visited_l,0,sizeof(Visited_l));//-2 means not visited
   memset(Visited_r,0,sizeof(Visited_r));//-2 means not visited
   flag=true;
   for(i=0;i<L_size;++i){
    if(Ptr_l[i]==-1){
     Visited_l[i]=1;
     Father_l[i]=-1;
     flag=false;
    }
   }
   if(flag) break;
   while(1){
    flag=true;
    for(i=0;i<L_size;++i){
     if(Visited_l[i]==1){
      for(j=0;j<Edge_lsize[i];++j){
       if(Visited_r[Edge_left[i][j]]==0&&Ptr_l[i]!=Edge_left[i][j]){
        flag=false;
        Visited_r[Edge_left[i][j]]=1;
        Father_r[Edge_left[i][j]]=i;
        if(Ptr_r[Edge_left[i][j]]==-1){
         //change edge
         t=Edge_left[i][j];
         do{
          tf=Father_r[t];
          Ptr_r[t]=tf;
          Ptr_l[tf]=t;
          t=Father_l[tf];          
         }while(t!=-1);

         goto OUT;
        }

       }
      }
      Visited_l[i]=2;
     }
    }
    if(flag) break;
    flag=true;

    for(i=0;i<R_size;++i){
     if(Visited_r[i]==1){
      if(Visited_l[ Ptr_r[i] ]==0){
       flag=false;
       Visited_l[Ptr_r[i]]=1;
       Father_l[Ptr_r[i]]=i;
      }
      Visited_r[i]=2;
     }
    }
    if(flag) break;

   }
   break;
OUT:
   continue;
  }
 /* for(i=0;i<L_size;++i)
   printf("%d %d\n",i,Ptr_l[i]);
  printf("\n\n");
 */
  for(i=0;i<L_size;++i)
   if(Ptr_l[i]==-1) break;
  if(i==L_size) printf("YES\n");
  else printf("NO\n");
 }
 return 0;
}

本文地址：http://com.8s8s.com/it/it35348.htm