社区讨论
萌新妹子刚学oi,不会写网络流,求大佬帮个忙
P3386【模板】二分图最大匹配参与者 11已保存回复 17
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 17 条
- 当前快照
- 1 份
- 快照标识符
- @mi7wo5ip
- 此快照首次捕获于
- 2025/11/21 04:50 4 个月前
- 此快照最后确认于
- 2025/11/21 06:34 4 个月前
最大流跑最大匹配
CPP#include<cstdio>
#include<queue>
#include<cstring>
#include<iostream>
const int inf = 1 << 29,N = 1e5 + 100,M = 1e6 + 100;
int super;
using namespace std;
int n,m,s,t,d[N],ans,p;
queue<int>q;
bool v[N];
int head[N],cnt = 1;
struct edge{
int to,nxt,dis;
}e[M];
void add(int from,int to,int dis){
e[++cnt].to = to;
e[cnt].dis = dis;
e[cnt].nxt = head[from];
head[from] = cnt;
}
bool bfs(){
memset(d,0,sizeof d);
while(!q.empty()) q.pop();
q.push(s);
d[s] = 1;
while(!q.empty()){
int x = q.front();
q.pop();
for(int i = head[x]; i ;i = e[i].nxt){
if(e[i].dis && !d[e[i].to]){
q.push(e[i].to);
d[e[i].to] = d[x] + 1;
if(e[i].to == t) return 1;
}
}
}
return 0;
}
int dinic(int x,int flow){
if(x == super || flow == 0) return flow;
int rest = flow,k;
for(int i = head[x]; i && rest;i = e[i].nxt){
if(e[i].dis && d[e[i].to] == d[x] + 1){
k = dinic(e[i].to,min(rest,e[i].dis));
if(!k) d[e[i].to] = 0;
e[i].dis -= k;
e[i ^ 1].dis += k;
rest -= k;
}
}
return flow - rest;
}
int main(){
scanf("%d %d %d",&n,&m,&p);
super = n+m+1;
for(int i = 1;i <= n;i ++) add(0,i,1);
for(int i = n+1;i <= n+m;i ++) add(i,super,1);
for(int i = 1;i <= p;i ++){
int u,v;
scanf("%d %d",&u,&v);
add(u,v,1);
}
int flow = 0;
while(bfs()){
while((flow = dinic(0,inf))) ans += flow;
}
printf("%d\n",ans);
return 0;
}
回复
共 17 条回复,欢迎继续交流。
正在加载回复...