poj1274 最大二分匹配

本文主要是介绍poj1274 最大二分匹配，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include<iostream>
#include<cstring>
using namespace std;
const int MAXN = 1000; 
int uN, vN;              // u, v数目，要初始化！！！ 
bool g[MAXN][MAXN];    // g[i][j] 表示xi与yj相连 
int xM[MAXN], yM[MAXN]; // xM[i]:cow i已经被分配到stall xM[i];  stall j 已经被分配给cow yM[j]
bool chk[MAXN];          // 辅助量检查某轮y[v]是否被check  
bool SearchPath(int u){ int v; for(v = 0; v < vN; v++) if(g[u][v] && !chk[v]) { chk[v] = true; //从u--->v //改为//u<-----vif(yM[v] == -1 || SearchPath(yM[v]))//如果已经存在于v相连的u的匹配 { yM[v] = u; xM[u] = v;return true ; } } return false ; 
} 
int MaxMatch(){ int u, ret = 0 ; memset(xM, -1, sizeof (xM)); memset(yM, -1, sizeof (yM)); for(u = 0; u < uN; u++) if(xM[u] == -1){ memset(chk, false, sizeof (chk)); if(SearchPath(u)) ret++; } return ret; 
} int main()
{int i,j,t,N,M,m,res;    //N:cows,M:stallswhile(cin>>N>>M){uN=N;vN=M;memset(g,0,sizeof(g));for(i=0;i<N;i++)    //fir each cows{cin>>t;        for(j=0;j<t;j++)    //for each stalls the cow like{cin>>m;g[i][m-1]=1;}}cout<<MaxMatch()<<endl;}return 0;
}

这篇关于poj1274 最大二分匹配的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---