MnZn 求助:玄学无输出
查看原帖
MnZn 求助:玄学无输出
372299
超级玛丽王子楼主2021/3/5 12:43

RT,完全按照匈牙利板子写的,布吉岛这是为什么

#include <bits/stdc++.h>
using namespace std;
const int N=10050;
int cnt,head[105],to[N],nxt[N];
int match[105];
bool rboy[105];
int n,m;
inline int read() {
	char ch=getchar();
	int x=0,f=1;
	while(ch<'0'||ch>'9') if(ch=='-') f=-1;
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	return x*f;
}
inline void add(int u, int v)  {
	to[++cnt]=v,nxt[cnt]=head[u],head[u]=cnt;
}
bool dfs(int x) {
	for(int e=head[x];e;e=nxt[e]) {
		int v=to[e];
		if(!rboy[v]) {
			rboy[v]=true;
			if(!match[v]||dfs(match[v])) {
				match[v]=x;
				return true;
			}
		}
	}
	return false;
}
int main(void) {
	m=read(),n=read();
	n-=m;
	int u=read(),v=read();
	while((u!=-1)&&(v!=-1)) {
		add(u,v);
		u=read(),v=read();
	}
	int sum=0;
	for(int i=1;i<=m;++i) {
		memset(rboy,0,sizeof(rboy));
		sum+=dfs(i);
	}
	printf("%d\n",sum);
	for(int i=m+1;i<=m+n;++i) {
		if(match[i]) printf("%d %d\n",match[i],i);
	}
	return 0;
}

2021/3/5 12:43
加载中...