admin 管理员组

文章数量: 887021

模板

P3386 【模板】二分图最大匹配

匈牙利算法思想：遍历左部点，对于每个点判断其是否为一条增广路的端点。

核心代码段：

变量解释：a[ i ][ j ]代表左部点与右部点是否有连线，vis为判断是否访问过（对于每一个左部点 i 的dfs时要先将其初始化），对于每一个右部点的j ，与其形成匹配边的左部点为pre[ j ]，即       （pre[ j ]，j）是一条匹配边。假如j是一个未盖点（即该点不在匹配中），则pre[ j ]=0

bool a[1005][1005],vis[1005];
int pre[1005],e,m,n;
bool dfs(int i){for(int j=1;j<=m;j++){if((vis[j]==0) && (a[i][j])){vis[j]=1;if((pre[j]==0) || dfs(pre[j])){pre[j]=i;return 1;}}}return 0;
}

完整AC代码：

#include<bits/stdc++.h>
using namespace std;
bool a[1005][1005],vis[1005];
int pre[1005],e,m,n;
bool dfs(int i){for(int j=1;j<=m;j++){if((vis[j]==0) && (a[i][j])){vis[j]=1;if((pre[j]==0) || dfs(pre[j])){pre[j]=i;return 1;}}}return 0;
}
int main(){memset(a,0,sizeof(a));memset(vis,0,sizeof(vis));memset(pre,0,sizeof(pre));cin>>n>>m>>e;for(int i=1;i<=e;i++){int u,v;cin>>u>>v;a[u][v] = 1;}int ans=0;for(int i=1;i<=n;i++){ans+=dfs(i);memset(vis,0,sizeof(vis));}cout<<ans;
}

本文标签： 模板

版权声明：本文标题：模板 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1686859149h42657.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。