匈牙利算法
- #include <bits/stdc++.h>
- using namespace std;
- const int maxnx=1e3+5;
- const int maxny=1e3+5;
- const int maxm=2e6+5;
- int nx,ny,m;
- int my[maxny];
- int vis[maxnx];
- struct edge{
- int next,to;
- }E[maxm];
- int tot=0,head[maxnx];
- void addedge(int u,int v){
- E[++tot].to=v;
- E[tot].next=head[u];
- head[u]=tot;
- }
- int find_path(int u){
- if(vis[u])return 0;
- vis[u]=1;
- for(int i=head[u];i>0;i=E[i].next){
- int v=E[i].to;
- if(my[v]==0||find_path(my[v])){
- my[v]=u;
- return 1;
- }
- }
- return 0;
- }
- int main(){
- int nx,ny,m;
- cin>>nx>>ny>>m;
- for(int i=1;i<=m;i++){
- int u,v;
- scanf("%d%d",&u,&v);
- if(u>nx||v>ny) continue;
- addedge(u,v);
- }
- int ans=0;
- for(int i=1;i<=nx;i++){
- memset(vis,0,sizeof(vis));
- if(find_path(i)){
- ans++;
- }
- }
- printf("%d\n",ans);
- }
二分图问题
来源: http://www.bubuko.com/infodetail-3265526.html