这道题不能建双向边?
查看原帖
这道题不能建双向边?
545986
Jerrycyx楼主2022/7/7 16:49

RT,这是单向边的结果,这是双向边的结果

按理说不是应该建双向边吗?

代码:

#include<cstdio>
#include<cstring>

#define N 5005
#define M 5005
#define E 100005

using namespace std;

int n,e;
int m;
int ans=0;

struct Allan{
	int to;
	int next;
}edge[E<<1];
int edge_cnt=0;
int head[N+M];
void add(int from,int to)
{
	edge_cnt++;
	edge[edge_cnt].to=to;
	edge[edge_cnt].next=head[from];
	head[from]=edge_cnt;
	return;
}

bool visit[N+M];
int match[N+M];
bool DFS(int x)
{
	for(int i=head[x];i;i=edge[i].next)
	{
		int y=edge[i].to;
		if(!visit[y])
		{
			visit[y]=true;
			if(!match[y]||DFS(match[y]))
			{
				match[y]=x;
				return true;
			}
		}
	}
	return false;
}

int main()
{
	scanf("%d%d%d",&n,&m,&e);
	for(int i=1;i<=e;i++)
	{
		int from,to;
		scanf("%d%d",&from,&to);
		add(from,to+n);
		add(to+n,from);
	}
	for(int i=1;i<=n+m;i++)
	{
		memset(visit,false,sizeof(visit));
		if(DFS(i)) ans++;
	}
	printf("%d\n",ans);
	return 0;
}
2022/7/7 16:49
加载中...