这里有两份我写的网络流模板代码,在 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;
}