社区讨论

萌新妹子刚学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 条回复,欢迎继续交流。

正在加载回复...