萌新刚学 OI,网络流模板题求教
  • 板块题目总版
  • 楼主NightTide
  • 当前回复3
  • 已保存回复3
  • 发布时间2022/8/8 08:53
  • 上次更新2023/10/27 16:31:17
查看原帖
萌新刚学 OI,网络流模板题求教
547908
NightTide楼主2022/8/8 08:53

这里有两份我写的网络流模板代码,在 bfs 中,正常情况应该初始化源点的流量为 INF,但是我一开始写的时候初始化了汇点的流量为 INF。两种写法都是对的,问一下这两种写法是都是正确的还是后面的是错误的?

#include<bits/stdc++.h>
#define MAXN 210
#define MAXM 5010
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
struct edge{
    ll pre,fr,to,flow;
};
edge e[MAXM << 1];
ll n, m, s, t, cnt = 1, ans;
ll head[MAXN], flow[MAXN], path[MAXN];
bool vis[MAXN];
void add_edge(ll u, ll v, ll w){
    e[++cnt].pre = head[u];
    e[cnt].to = v; e[cnt].fr = u; e[cnt].flow = w;
    head[u] = cnt;
}
bool bfs(ll sour, ll sink){
    memset(vis, 0, sizeof(vis));
    queue<ll> q;
    q.push(sour); vis[sour] = true;
    flow[sour] = INF;// here,这里是初始化源点
    while(!q.empty()){
        ll now = q.front(); q.pop();
        for(ll i = head[now]; i; i = e[i].pre){
            if(!vis[e[i].to] && e[i].flow > 0){
                path[e[i].to] = i;
                flow[e[i].to] = min(flow[now], e[i].flow);
                vis[e[i].to] = true;
                q.push(e[i].to);
            }
        }
    }
    if(vis[sink]) return true;
    else return false;
}
void back_track(ll sour, ll sink){
    ll now = sink;
    while(now != sour){
        e[path[now]].flow -= flow[sink];
        e[path[now] ^ 1].flow += flow[sink];
        now = e[path[now]].fr;
    }
}
int main(){
    scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
    for(ll i = 1; i <= m; i++){
        ll u, v, w;
        scanf("%lld%lld%lld",&u,&v,&w);
        add_edge(u, v, w); add_edge(v, u, 0);
    }
    flow[s] = INF;
    while(bfs(s, t)){
        back_track(s, t);
        ans += flow[t];
    }
    printf("%lld\n",ans);
    return 0;
}
#include<bits/stdc++.h>
#define MAXN 210
#define MAXM 5010
#define INF 0x3f3f3f3f
using namespace std;
typedef long long ll;
struct edge{
    ll pre,fr,to,flow;
};
edge e[MAXM << 1];
ll n, m, s, t, cnt = 1, ans;
ll head[MAXN], flow[MAXN], path[MAXN];
bool vis[MAXN];
void add_edge(ll u, ll v, ll w){
    e[++cnt].pre = head[u];
    e[cnt].to = v; e[cnt].fr = u; e[cnt].flow = w;
    head[u] = cnt;
}
bool bfs(ll sour, ll sink){
    memset(vis, 0, sizeof(vis));
    queue<ll> q;
    q.push(sour); vis[sour] = true;
    flow[sink] = INF;// here,这里初始化了汇点,还是 AC 了
    while(!q.empty()){
        ll now = q.front(); q.pop();
        for(ll i = head[now]; i; i = e[i].pre){
            if(!vis[e[i].to] && e[i].flow > 0){
                path[e[i].to] = i;
                flow[e[i].to] = min(flow[now], e[i].flow);
                vis[e[i].to] = true;
                q.push(e[i].to);
            }
        }
    }
    if(vis[sink]) return true;
    else return false;
}
void back_track(ll sour, ll sink){
    ll now = sink;
    while(now != sour){
        e[path[now]].flow -= flow[sink];
        e[path[now] ^ 1].flow += flow[sink];
        now = e[path[now]].fr;
    }
}
int main(){
    scanf("%lld%lld%lld%lld",&n,&m,&s,&t);
    for(ll i = 1; i <= m; i++){
        ll u, v, w;
        scanf("%lld%lld%lld",&u,&v,&w);
        add_edge(u, v, w); add_edge(v, u, 0);
    }
    flow[s] = INF;
    while(bfs(s, t)){
        back_track(s, t);
        ans += flow[t];
    }
    printf("%lld\n",ans);
    return 0;
}
2022/8/8 08:53
加载中...