二分圖匹配實(shí)例代碼及整理

二分圖匹配實(shí)例代碼及整理

為依蘭等地區(qū)用戶提供了全套網(wǎng)頁設(shè)計(jì)制作服務(wù)，及依蘭網(wǎng)站建設(shè)行業(yè)解決方案。主營(yíng)業(yè)務(wù)為成都做網(wǎng)站、網(wǎng)站建設(shè)、依蘭網(wǎng)站設(shè)計(jì)，以傳統(tǒng)方式定制建設(shè)網(wǎng)站，并提供域名空間備案等一條龍服務(wù)，秉承以專業(yè)、用心的態(tài)度為用戶提供真誠(chéng)的服務(wù)。我們深信只要達(dá)到每一位用戶的要求，就會(huì)得到認(rèn)可，從而選擇與我們長(zhǎng)期合作。這樣，我們也可以走得更遠(yuǎn)！

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)); //初始化頂標(biāo) 
  memset(ly, 0, sizeof(ly)); //ly[i]為0 
  for(int i = 0; i < n; ++i) //lx[i]為權(quán)值最大的邊 
    for(int j = 0; j < n; ++j) 
      lx[i] = max(lx[i], map[i][j]); 
  for(int i = 0; i < n; ++i) //對(duì)n個(gè)點(diǎ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在交錯(cuò)樹中 
          if(visitx[j]) 
            for(int k = 0; k < n; ++k) //y在交錯(cuò)樹外 
              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) //更新頂標(biāo) 
        { 
          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) //權(quán)值相加 
      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++)//看能否回溯一個(gè)出去 
      { 
        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; 
}

以上就是二分圖匹配的實(shí)現(xiàn)代碼，如有疑問請(qǐng)留言，或者到本站社區(qū)交流討論，感謝閱讀，希望能幫助到大家，謝謝大家對(duì)本站的支持！

網(wǎng)頁題目：二分圖匹配實(shí)例代碼及整理
當(dāng)前鏈接：http://muchs.cn/article0/joosoo.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供電子商務(wù)、網(wǎng)站導(dǎo)航、企業(yè)建站、動(dòng)態(tài)網(wǎng)站、做網(wǎng)站、App設(shè)計(jì)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)

成都網(wǎng)站建設(shè)公司