社区讨论
【㵘】一个不奇怪的请求
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 条回复,欢迎继续交流。
正在加载回复...