社区讨论

求助,用vector的匈牙利只有55分

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

讨论操作

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

当前回复
2 条
当前快照
1 份
快照标识符
@mi6gwgs0
此快照首次捕获于
2025/11/20 04:41
4 个月前
此快照最后确认于
2025/11/20 04:41
4 个月前
查看原帖
如题,求大佬解决
CPP
#include<cstdio>
#include<cstring>
#include<vector>
#define For(i,j,k) for(int i=j;i<=k;i++)
using namespace std;
inline int read()
{
    int l=1,x=0; char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
    if (ch=='-') ch=getchar(),l=-1;
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*l;
}
vector<int> a[1005];
int vis[1005],mat[1005];
bool dfs(int n){
    for(int i=0;i<a[n].size();i++){
        int v=a[n][i];
        if (!vis[v]){
            vis[v]=1;
            if (!mat[v]||dfs(mat[v])){
                mat[v]=n; return 1;
            }
        }
    }
    return 0;
}
int main(){
    int n,e,ans=0,m,x,y; n=read(),m=read(),e=read();
    For(i,1,e){
        x=read(),y=read();
        a[x].push_back(y);
    }
    For(i,1,n){
        memset(vis,0,sizeof(vis));
        if (dfs(i)) ans++;
    }
    printf("%d\n",ans);
    return 0;
}

回复

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

正在加载回复...