社区讨论
求助,用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 条回复,欢迎继续交流。
正在加载回复...