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

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

1、匈牙利算法

HDU 1150

#include<stdio.h>
#include<string.h>
#include<algorithm>
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<m;i++)
  {
    if(vis[i]==0&&mpt[x][i]==1)
    {
      vis[i]=1;
      if(use[i]==-1||hungary(use[i]))
      {
        use[i]=x;
        return 1;
      }
    }
  }
  return 0;
}
int main()
{
  while(scanf("%d",&n)!=EOF,n)
  {
    scanf("%d%d",&m,&k);
    int a,b,c;
    memset(mpt,0,sizeof(mpt));
    for(int i=1;i<=k;i++)
    {
      scanf("%d%d%d",&c,&a,&b);
      mpt[a][b]=1;
    }
    int ans=0;
    memset(use,-1,sizeof(use));
    for(int i=1;i<n;i++)
    {
      if(hungary(i))
      {
        ans++;
      }
      memset(vis,0,sizeof(vis));
    }
    printf("%d\n",ans);
  }
  return 0;
}

2、KM算法

HDU 2255

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

#include<iostream>
#include<cstdio>
#include<cstring>
#include<climits>
#include<algorithm>
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<stdio.h>
#include<string.h>
#include<algorithm>
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]<num[i])//满足条件
      {
        dp[i][use[i]++]=x;
        return 1;
      }
      //不满足则寻找增广路
      for(int j=0;j<use[i];j++)//看能否回溯一个出去
      {
        if(hungary(dp[i][j]))
        {
          dp[i][j]=x;
          return 1;
        }
      }
    }
  }
  return 0;
}
int main()
{
  while(scanf("%d%d",&n,&m)!=EOF)
  {
    for(int i=1;i<=n;i++)
    {
      for(int j=1;j<=m;j++)
      {
        scanf("%d",&mpt[i][j]);
      }
    }
    for(int i=1;i<=m;i++)
      scanf("%d",&num[i]);
    int ans=0;
    memset(use,0,sizeof(use));
    for(int i=1;i<=n;i++)
    {
      memset(vis,0,sizeof(vis));
      if(!hungary(i))
      {
        ans=1;
        break;
      }
    }
    if(ans==0)
    {
      printf("YES\n");
    }
    else printf("NO\n");
  } 

  return 0;
}

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