【㵘】一个不奇怪的请求
查看原帖
【㵘】一个不奇怪的请求
312306
LJ07楼主2022/5/14 19:06

本题数据也太水了吧,月赛是使用本题检测二分图匹配,结果下面代码过了

#include<bits/stdc++.h>
#define int long long
#define U(i,l,r) for(int i(l),END##i(r);i<=END##i;++i)
#define D(i,r,l) for(int i(r),END##i(l);i>=END##i;--i)
using namespace std;
inline int qr() {
	char c; bool f(true);
	while(!isdigit(c=getchar()))f=c!='-';
	int x(c^48);
	while(isdigit(c=getchar()))x=x*10+(c^48);
	return f?x:-x;
}
const int N(1e6+5);
int n,m,e;
namespace Graph {
	vector<int> g[N+5];
	int match[N+5],tims[N+5];
	bool findd(int u,int tag) {
		if(tims[u]==tag)
			return false;
		tims[u]=tag;
		for(auto v:g[u]) {
			if(!match[v]||findd(match[v],tag))
				return match[v]=tag,true;
		}
		return false;
	}
} ; // namespace Graph
using namespace Graph;
signed main() {
	n=qr(),m=qr(),e=qr();
	U(i,1,e) {
		int u(qr()),v(qr());
		g[u].push_back(v);
	}
	int ans(0);
	U(i,1,n) ans+=findd(i,i);
	printf("%d",ans);
}

显然match[v]=tag应该改成match[v]=u,但是数据把错误代码给放过了

2022/5/14 19:06
加载中...