社区讨论

求大佬,牙利算法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 条回复,欢迎继续交流。

正在加载回复...