社区讨论

样例过了,1AC 匈牙利算法求助

P3386【模板】二分图最大匹配参与者 3已保存回复 3

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
3 条
当前快照
1 份
快照标识符
@lob9izmt
此快照首次捕获于
2023/10/29 17:22
2 年前
此快照最后确认于
2023/11/03 23:23
2 年前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
vector<int>q[500005];
int girl[500005];//
bool us[500005];//是否访问过
bool findgirl(int x){
     for(int i=0;i<q[x].size();i++){
        int o=q[x][i];
     if(us[o]==false) {
           us[o]=true;
           if(girl[o]==0||findgirl(girl[o])){
                girl[o]=x;
                return true;
           }
           }
       return false;
}
}//算法主体
int main(){
    int n,m,e,ans=0;
    cin>>n>>m>>e;
    for(int i=1;i<=e;i++){
            int u,v;
            cin>>u>>v;
            q[u].push_back(v);
            }//建边
     for(int i=1;i<=n;i++){
             if(findgirl(i)==true) ans++;
}
    cout<<ans<<endl;
    return 0;
}

回复

3 条回复,欢迎继续交流。

正在加载回复...