社区讨论

求助dalao(wa了第5个点)(玄关)

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

讨论操作

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

当前回复
2 条
当前快照
1 份
快照标识符
@lztmplat
此快照首次捕获于
2024/08/14 17:08
2 年前
此快照最后确认于
2024/08/14 19:45
2 年前
查看原帖
代码如下:
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n1,n2,m;
int idx;
int mc[100001];
int sum=0;
bool st[100001];
struct cmp
{
	int h;
	int e;
	int ne;
}a[100001];
void add(int x,int y)
{
	a[idx].e=y;
	a[idx].ne=a[x].h;
	a[x].h=idx++;
}
bool find(int x)
{
	for(int i=a[x].h;i!=-1;i=a[i].ne)
	{
		int j=a[i].e;
		if(!st[j])
		{
			st[j]=true;
			if(mc[j]==0||find(mc[j]))
			{
				mc[j]=x;
				return true;
			}
		}
	}
	return false;
}
signed main()
{
	cin>>n1>>n2>>m;
	for(int i=1;i<=m;i++)
	{
		a[i].h=-1;
	}
	while(m--)
	{
		int a,b;
		cin>>a>>b;
		add(a,b);
	}
	for(int i=1;i<=n1;i++)
	{
 		memset(st,false,sizeof(st));
 		if(find(i))
		{
			sum++;	
		}
 	}
 	cout<<sum;
 	
 	return 0;
}

回复

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

正在加载回复...