阿坝州网站建设公司

二分图匹配实例代码及整理

二分图匹配实例代码及整理

为依兰等地区用户提供了全套网页设计制作服务，及依兰网站建设行业解决方案。主营业务为成都做网站、网站建设、依兰网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！

1、匈牙利算法

HDU 1150

#include 
#include 
#include 
using namespace std; 
int m,n,k; 
int vis[105]; 
int mpt[105][105]; 
int use[105]; 
int hungary(int x) 
{ 
  for(int i=1;i

2、KM算法

HDU 2255

看了很多资料都还不是很懂、、先贴别人的模板

#include 
#include 
#include 
#include 
#include 
using namespace std; 
#define N 310 
int map[N][N]; 
bool visitx[N], visity[N]; 
int lx[N], ly[N]; 
int match[N]; 
int n; 
 
bool Hungary(int u) //匈牙利算法 
{ 
  visitx[u] = true; 
  for(int i = 0; i < n; ++i) 
  { 
    if(!visity[i] && lx[u] + ly[i] == map[u][i]) 
    { 
      visity[i] = true; 
      if(match[i] == -1 || Hungary(match[i])) 
      { 
        match[i] = u; 
        return true; 
      } 
    } 
  } 
  return false; 
} 
 
void KM_perfect_match() 
{ 
  int temp; 
  memset(lx, 0, sizeof(lx)); //初始化顶标 
  memset(ly, 0, sizeof(ly)); //ly[i]为0 
  for(int i = 0; i < n; ++i) //lx[i]为权值最大的边 
    for(int j = 0; j < n; ++j) 
      lx[i] = max(lx[i], map[i][j]); 
  for(int i = 0; i < n; ++i) //对n个点匹配 
  { 
    while(1) 
    { 
      memset(visitx, false, sizeof(visitx)); 
      memset(visity, false, sizeof(visity)); 
      if(Hungary(i)) //匹配成功 
        break; 
      else //匹配失败，找最小值 
      { 
        temp = INT_MAX; 
        for(int j = 0; j < n; ++j) //x在交错树中 
          if(visitx[j]) 
            for(int k = 0; k < n; ++k) //y在交错树外 
              if(!visity[k] && temp > lx[j] + ly[k] - map[j][k]) 
                temp = lx[j] + ly[k] - map[j][k]; 
        for(int j = 0; j < n; ++j) //更新顶标 
        { 
          if(visitx[j]) 
            lx[j] -= temp; 
          if(visity[j]) 
            ly[j] += temp; 
        } 
      } 
    } 
  } 
} 
 
int main() 
{ 
  int ans; 
  while(scanf("%d", &n) != EOF) 
  { 
    ans = 0; 
    memset(match, -1, sizeof(match)); 
    for(int i = 0; i < n; ++i) 
      for(int j = 0; j < n; ++j) 
        scanf("%d", &map[i][j]); 
    KM_perfect_match(); 
    for(int i = 0; i < n; ++i) //权值相加 
      ans += map[match[i]][i]; 
    printf("%d\n", ans); 
  } 
  return 0; 
}

3、多重匹配

HDU  3605 Escape

#include 
#include 
#include 
using namespace std; 
int n,m; 
int num[15]; 
int mpt[100005][15]; 
int vis[15]; 
int use[15]; 
int dp[15][100005]; 
int hungary(int x) 
{ 
  for(int i=1;i<=m;i++) 
  { 
    if(vis[i]==0&&mpt[x][i]==1) 
    { 
      vis[i]=1; 
      if(use[i]

以上就是二分图匹配的实现代码，如有疑问请留言，或者到本站社区交流讨论，感谢阅读，希望能帮助到大家，谢谢大家对本站的支持！


文章标题：二分图匹配实例代码及整理
地址分享：http://azwzsj.com/article/joosoo.html

其他资讯