題意：求二分圖的最大匹配數量

模版如下：

//二分圖匹配（匈牙利算法的DFS實現） //初始化：g[][]兩邊頂點的劃分情況 //建立g[i][j]表示i->j的有向邊就可以了，是左邊向右邊的匹配 //g沒有邊相連則初始化為0 //uN是匹配左邊的頂點數，vN是匹配右邊的頂點數 //調用：res=hungary();輸出最大匹配數 //優點：適用于稠密圖，DFS找增廣路，實現簡潔易于理解 //時間復雜度:O(VE) //*******************

?

#include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <queue> #include <typeinfo> #include <fstream> typedef long long ll; using namespace std; //freopen("D.in","r",stdin); //freopen("D.out","w",stdout); const int MAXN=510; int uN,vN;//u,v數目 int g[MAXN][MAXN]; int linker[MAXN]; bool used[MAXN]; bool dfs(int u)//從左邊開始找增廣路徑 {int v;for(v=0;v<vN;v++)//這個頂點編號從0開始，若要從1開始需要修改if(g[u][v]&&!used[v]){used[v]=true;if(linker[v]==-1||dfs(linker[v])){//找增廣路，反向linker[v]=u;return true;}}return false;//這個不要忘了，經常忘記這句 } int hungary() {int res=0;int u;memset(linker,-1,sizeof(linker));for(u=0;u<uN;u++){memset(used,0,sizeof(used));if(dfs(u)) res++;}return res; }

A題代碼：

#include <cstdio> #include <cmath> #include <cstring> #include <ctime> #include <iostream> #include <algorithm> #include <set> #include <vector> #include <sstream> #include <queue> #include <typeinfo> #include <fstream> typedef long long ll; using namespace std; //freopen("D.in","r",stdin); //freopen("D.out","w",stdout); const int MAXN=510; int uN,vN;//u,v數目 int g[MAXN][MAXN]; int linker[MAXN]; bool used[MAXN]; bool dfs(int u)//從左邊開始找增廣路徑 {int v;for(v=0;v<vN;v++)//這個頂點編號從0開始，若要從1開始需要修改if(g[u][v]&&!used[v]){used[v]=true;if(linker[v]==-1||dfs(linker[v])){//找增廣路，反向linker[v]=u;return true;}}return false;//這個不要忘了，經常忘記這句 } int hungary() {int res=0;int u;memset(linker,-1,sizeof(linker));for(u=0;u<uN;u++){memset(used,0,sizeof(used));if(dfs(u)) res++;}return res; } int main() {memset(g,0,sizeof(g));int b[MAXN],g1[MAXN];cin>>uN;for(int i=0;i<uN;i++)cin>>b[i];cin>>vN;for(int i=0;i<vN;i++)cin>>g1[i];for(int i=0;i<uN;i++){for(int j=0;j<vN;j++){if(fabs(b[i]-g1[j])<=1)g[i][j]=1;}}cout<<hungary()<<endl;return 0; }

?

總結

以上是生活随笔為你收集整理的CF 277.5 B.BerSU Ball 二分图的最大匹配 模版题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。