zercal
C++博客 首页 新随笔 联系 聚合 管理
  10 Posts :: 0 Stories :: 0 Comments :: 0 Trackbacks
匈牙利算法求二分图最大匹配
#include <stdio.h>
#include <cstring>

//匈牙利算法
int  xv=5,yv=5,n=5;     // 顶点数（数字5认你定） 
int  g[5][5];     // g[i][j]=1 表示 xi与yj相邻 
int  sy[5];     // 辅助：当轮被搜过的y点都是1  
int  cnt,xm[5],ym[5];  // 输出  
void  init()
{
    cnt=0 ;
    memset(g, 0 ,sizeof(g));
    memset(xm,-1,sizeof(xm));
    memset(ym,-1,sizeof(ym));
} 
int path(int u) // 返回是否找到增广路（递归，时间复杂度O（n*n）） 
{
    int v;
    for(v=0;v<yv;v++)
    {
        if((g[u][v]==1)&&(sy[v]==0))  
        { 
            sy[v]=1;
            if((ym[v]==-1)||(path(ym[v])==1))
            {
                xm[u]=v;ym[v]=u;
                return 1;
            } 
        }
    }
    return 0;   
} 
void main()
{
    int  i,j;
    //初始化
    init();
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            scanf("%d",&g[i][j]);
        }
    }
    //核心
    for(i=0;i<xv;i++)
    {
        if(xm[i]==-1)
        {
            memset(sy,0,sizeof(sy));
            cnt+=path(i);
        }
    }
    //打印
    printf("sum=%d",cnt);
}
posted on 2007-10-06 19:57 zercal 阅读(361) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理