Code666 (代码贴、代码片段)

[C] 二分匹配部分 →→→→→进入此内容的聊天室

来自 , 2021-01-01, 写在 C, 查看 142 次.
URL http://www.code666.cn/view/f708f064
  1. int n1,n2,edge;
  2. int map[M][M];//邻接矩阵
  3. int vis[M];//n2,集合中对每一个点的访问做标记
  4. int match[M};//表示当前n1中可以与 n2 集合中相邻的点
  5. void init( )
  6. {
  7.         int n1,n2,edge;
  8.         scanf("%d%d%d",&n1,&n2,&edge);
  9.         memset(map,0,sizeof(map));
  10.         memset(match,0,sizeof(match));
  11.         for(int i=0;i<edge;i++)
  12.         {
  13.                 int x,y;
  14.                 scanf("%d%d",&x,&y);
  15.                 map[x][y]=1;
  16.         }
  17. }
  18.  
  19. int find(int node)//是否存在n1集合中以结点node开始的增广路
  20. {
  21.   for(int i=1;i<=n2;i++)
  22.     if(map[node][i]&&!vis[i]==0)//如果节点 i 与 node相邻并且未访问过
  23.         {
  24.           vis[i]=1;
  25.           if(match[i]==-1||find(match[i]))//如果找到一个未覆盖点i中或从与i相邻的节点出发有增广路
  26.           {
  27.             match[i]=node;
  28.                 return 1;      
  29.           }    
  30.         }      
  31.   return 0;
  32. }
  33.  
  34. int result_max_match(int n1)//返回最大二分匹配值
  35. {
  36.   int i,ans=0;
  37.   for(i=1;i<=n1;i++)
  38.   {
  39.         memset(vis,0,sizeof(vis));//注意初始化
  40.         if(find(i))
  41.           ans++;
  42.   }
  43.   return ans;
  44. }

回复 "二分匹配部分"

这儿你可以回复上面这条便签

captcha

贴代码片段 - Code666