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

#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; } 

#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; } 

#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; }