perfect-match.cpp

来自「这是关于图论算法里面的一些代码,图论基本的思想代码的实现」· C++ 代码 · 共 42 行

bool dfs(int s)
{
 int i;
 cx[s]=true;
 for(i=0;i<cnt;i++)
 if(!cy[i]&& x[s]+y[i]==w[s][i])
 {
  cy[i]=true;
  if(match[i]==-1||dfs(match[i]))
  {
   match[i]=s;
   return true;
  }   
 } 
 return false;
}
void max_match()
{
 int i,j,k;
 int d,tmp;
 memset(match,0xff,sizeof(match));   
 for(i=0;i<cnt;i++)
 {
  while(true)
  {
   memset(cx,false,sizeof(cx));
   memset(cy,false,sizeof(cy));   
   if(dfs(i))break;
   d = 0x3fffffff;
   for(j=0;j<cnt;j++)
    if(cx[j])
     for(k=0;k<cnt;k++)
      if(!cy[k])
       d = d>(tmp=x[j]+y[k]-w[j][k]))?tmp:d;
   for(j=0;j<cnt;j++){
    if(cx[j])x[j]-=d;
    if(cy[j])y[j]+=d;
   }
  } 
 }
}