模板(不断完善ing)

二分图匹配

匈牙利算法

#include<bits/stdc++.h>
const int N = 1010;
int F[N],n,m,v[N];
struct edge{
    int next,to;
}e[N*N];
int cnt,last[N],tim,E;
void add(int a,int b){
    cnt++;e[cnt].to=b,e[cnt].next=last[a],last[a]=cnt;
}
bool find(int x){
    for(int i=last[x];i;i=e[i].next){
        if(v[e[i].to]==tim) continue;
        v[e[i].to]=tim;
        if(!F[e[i].to]||find(F[e[i].to])){
            F[e[i].to]=x;
            return 1;
        }
    }
    return 0;
}
int main(){
    scanf("%d %d %d",&n,&m,&E);
    for(int i=1;i<=E;++i){
        int u,v;
        scanf("%d %d",&u,&v);
        if(u>n||v>m) continue;
        add(u,v);
    }
    int ans=0;
    for(int i=1;i<=n;++i){
        tim++;
        ans+=find(i);
    }
    printf("%d\n",ans);
    return 0;
}
分类: 模板

0 条评论

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注