二分图最大匹配模板

今晚我们几个研究了这个题目。 二分图最大匹配模板，同时也是最小覆盖路径的模板。对应 POJ1422，水之。

#include <stdio.h>

/*

二分图最大匹配模板

最小覆盖路径模板 (最小路径=点数-最大二分匹配数)
*/

#include <string.h>//memset需要
#define Na 125//集合A数量
#define Nb 125//集合B数量

bool a2b[Na][Nb]/*关系矩阵*/,visited[Nb];/*单次查找是否已经查过*/
int link[Nb]/*集合B连接的前驱，指向A*/,A,B/*当前处理的A，B集合大小*/;

bool find(int x){//查找函数
  int i;
  for(i=1;i<=B;i++){
    if(!visited[i]&&a2b[x][i]){
      visited[i]=true;
      if(link[i]==-1||find(link[i])){
        link[i]=x;
        return true;
      }
    }
  }
  return false;
}

int main(){
  int itr,i,a,b,ans,cs;
  scanf("%d",&cs);
  while(cs--){
    scanf("%d%d",&A,&itr);
    B=A;//当前处理容量
    memset(a2b,0,sizeof(a2b));//初始化关系
    memset(link,-1,sizeof(link));//初始化B前驱连接
    ans=0;//二分匹配数量
    for(i=0;i<itr;i++){
      scanf("%d%d",&a,&b);
      a2b[a][b]=true;//关系建立
    }
    for(i=1;i<=A;i++){
      memset(visited,0,sizeof(visited));//每次匹配初始化
      if(find(i))ans++;//记数
    }
    printf("%dn",A-ans);//最小覆盖路径
  }
  return 0;
}