社区讨论
求大佬,牙利算法wa*8
P3386【模板】二分图最大匹配参与者 4已保存回复 4
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 4 条
- 当前快照
- 1 份
- 快照标识符
- @mi6xkpzm
- 此快照首次捕获于
- 2025/11/20 12:28 4 个月前
- 此快照最后确认于
- 2025/11/20 12:28 4 个月前
CPP
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
using namespace std;
#define INIT_CIN \
ios::sync_with_stdio(false);\
cin.tie(0);
const int maxn=1700001;
struct edge{
int u,v,w,nxt;
}e[maxn];
int fst[maxn],cnt;
inline void addedge(int u,int v,int w){
e[++cnt].u=u;e[cnt].v=v;e[cnt].w=w;
e[cnt].nxt=fst[u];
fst[u]=cnt;
return;
}
int n,m,ee;
int used[maxn],nxt[maxn];//used是否被匹配
//nxt 匹配到的是几号
int con_x[maxn],con_y[maxn];
inline bool Find(int x){
for(int i=fst[x];i;i=e[i].nxt){
int v=e[i].v;
if(!used[v]){
used[v]=1;
if(nxt[v]==0||Find(nxt[v])){
nxt[v]=x;
return true;
}
}
}
return false;
}
inline int match(){
int sum=0;
//memset(con_x,0,sizeof(con_x));
//memset(used,0,sizeof(used));
//memset(nxt,0,sizeof(nxt));
for(int i=1;i<=n;++i){
memset(used,0,sizeof(used));
//for(int j=1;j<=m;++j)used[j]=0;
if(Find(i))sum++;
}
return sum;
}
inline int read(){ int s=0,w=1; char ch=getchar(); while(ch<='0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();} while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar(); return s*w;}
int main(){
// INIT_CIN;
cin>>n>>m>>ee;
for(int i=1;i<=ee;++i){
int x,y;//cin>>x>>y;
x=read();y=read();
if(x<=n&&y<=m){//数据有坑
addedge(x,y,1);
addedge(y,x,1);
}
}
cout<<match();
return 0;
}
CPP感激不尽
回复
共 4 条回复,欢迎继续交流。
正在加载回复...