二分圖匹配摸板題。。。。

主要是用了匈牙利算法，，

主要思想還是 dfs。

匈牙利算法主要如下

bool dfs(int k) {for(int i=1;i<=r;i++){if(ed[k][i]&&!vis[i])//判斷此點是否使用過和是否聯(lián)通{vis[i]=true;//標記訪問if(!lin[i]||dfs(lin[i]))//如果 i 點沒有被連接或者i點連接的目標還有別的選擇{lin[i]=k;//連接二者return true;}}}return false; }

以下為AC代碼。。。主要還是多學(xué)習(xí)一下

?

?

?

?

#include<iostream> #include<cstdio> #include<cstring> #include<algorithm>using namespace std;const int maxn = 1005; int x,y; int l,r,m; bool ed[maxn][maxn]; bool vis[maxn]; int lin[maxn];bool dfs(int k) {for(int i=1;i<=r;i++){if(ed[k][i]&&!vis[i]){vis[i]=true;if(!lin[i]||dfs(lin[i])){lin[i]=k;return true;}}}return false; }int main() {scanf("%d%d%d",&l,&r,&m);for(int i=1;i<=m;i++){scanf("%d%d",&x,&y);ed[x][y]=1;}int ans=0;for(int i=1;i<=l;i++){memset(vis,false,sizeof(vis));if(dfs(i))ans++;}printf("%d\n",ans);return 0; }

?

總結(jié)

以上是生活随笔為你收集整理的洛谷 P3386的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。