社区讨论

【㵘】一个不奇怪的请求

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

讨论操作

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

当前回复
4 条
当前快照
1 份
快照标识符
@lo8vyhms
此快照首次捕获于
2023/10/28 01:27
2 年前
此快照最后确认于
2023/10/28 01:27
2 年前
查看原帖
本题数据也太水了吧,月赛是使用本题检测二分图匹配,结果下面代码过了
CPP
#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,但是数据把错误代码给放过了

回复

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

正在加载回复...