UOJ二分图最大匹配求助
  • 板块学术版
  • 楼主Nodlek
  • 当前回复1
  • 已保存回复1
  • 发布时间2021/7/23 23:32
  • 上次更新2023/11/4 13:30:37
查看原帖
UOJ二分图最大匹配求助
519187
Nodlek楼主2021/7/23 23:32

为什么这道题只能这样写

//2021/7/18

//2021/7/23

#include <cstdio>

#include <cstring>

using namespace std;

const int ma=250000;

struct Node
{
	int v;
	
	int nxt;
};

Node node[ma<<1];

int head[ma],mat[ma];

bool vis[ma];

int idx;

int l,r,m;

inline void add(int u,int v)
{
	node[++idx].v=v;
	
	node[idx].nxt=head[u];
	
	head[u]=idx;
} 

inline bool get_edge(int u)
{
	for(register int i=head[u];i;i=node[i].nxt)
	{
		int j=node[i].v;
		
		if(vis[j]==false)
		{
			vis[j]=true;
			
			if(mat[j]==0 || get_edge(mat[j])==true)
			{
				mat[j]=u;
				
				return true;
			}
		}
	}
	
	return false;
}

int main(void)
{
	scanf("%d%d%d",&l,&r,&m);
	
	while(m--)
	{
		int u,v;
		
		scanf("%d%d",&u,&v);
		
		add(v,u);
	}
	
	int res=0;
	
	for(register int i=1;i<=r;i++)
	{	
		memset(vis,false,sizeof(vis));
		
		if(get_edge(i)==true)
		{
			res++;
		}
	}
	
	printf("%d\n",res);
	
	for(register int i=1;i<=l;i++)	
	{
		printf("%d\n",mat[i]);
	}
	
	return 0;
} 

而不能这样写

//2021/7/18

//2021/7/23

#include <cstdio>

#include <cstring>

using namespace std;

const int ma=250000;

struct Node
{
	int v;
	
	int nxt;
};

Node node[ma<<1];

int head[ma],mat[ma];

bool vis[ma];

int idx;

int l,r,m;

inline void add(int u,int v)
{
	node[++idx].v=v;
	
	node[idx].nxt=head[u];
	
	head[u]=idx;
} 

inline bool get_edge(int u)
{
	for(register int i=head[u];i;i=node[i].nxt)
	{
		int j=node[i].v;
		
		if(vis[j]==false)
		{
			vis[j]=true;
			
			if(mat[j]==0 || get_edge(mat[j])==true)
			{
				mat[j]=u;
				
				return true;
			}
		}
	}
	
	return false;
}

int main(void)
{
	scanf("%d%d%d",&l,&r,&m);
	
	while(m--)
	{
		int u,v;
		
		scanf("%d%d",&u,&v);
		
		add(u,v);
	}
	
	int res=0;
	
	for(register int i=1;i<=l;i++)
	{	
		memset(vis,false,sizeof(vis));
		
		if(get_edge(i)==true)
		{
			res++;
		}
	}
	
	printf("%d\n",res);
	
	for(register int i=1;i<=r;i++)	
	{
		printf("%d\n",mat[i]);
	}
	
	return 0;
} 

其中不一样的地方在于:

ac:add(v,u);
wa:add(u,v);
ac:
for(register int i=1;i<=r;i++)
{
	memset(vis,false,sizeof(vis));
    ...
}
wa:
for(register int i=1;i<=l;i++)
{
...
}
ac:
for(register int i=1;i<=l;i++)	
{
	printf("%d\n",mat[i]);
}
wa:
for(register int i=1;i<=r;i++)
{
	...
}

wa 的那种写法在洛谷上可以 AC,而且我感觉逻辑没啥问题。。

2021/7/23 23:32
加载中...