xialingn @ 2024-08-18 00:53:28
代码带有注释,求调
#include<bits/stdc++.h>
using namespace std;
const int maxn = 205;
const int maxm = 5005;
const int flow_max = 0x7fffffff;
long long capa[maxn][maxn], flow[maxn]; //记录残留网络的容量,标记从源点到当前节点实际还剩多少流量可用
int n, m, s, t, pre[maxn];//点、边、源点、汇点;记录前驱并用来判断是否在队列的数组;
queue<int> q;
int bfs(int src, int des) {
while(!q.empty()) q.pop(); //队列清空
for (int i=1; i <= n; i++) pre[i] = -1; //此时未记录前驱且都不在队列中
flow[src] = flow_max;
pre[src] = 0;
q.push(src);
while (!q.empty()) {
int v = q.front();
q.pop();
if (v == des) break;
for (int i=1; i <= n; i ++) { //未记录出边,直接遍历所有点
if(capa[v][i] > 0 && i != src && pre[i] == -1) { //存在路径且该点既不是源点之前也未探索过
q.push(i);
pre[i] = v;
flow[i] = min(capa[v][i], flow[v]);
}
}
}
if (pre[des] == -1) return -1; //残留图中不再存在增广路
else return flow[des]; //一条增广路径上的流入汇点的流量
}
int maxFlow(int src, int des ) {
long long increase = 0; //每个增广路径的流量
long long sumflow = 0;//总流量
while ((increase = bfs(src, des)) != -1) { //当图中还存在增广路径时
int k = des;
while(k != src) {
int last = pre[k];
capa[last][k] -= increase;
capa[k][last] += increase; //建立反向边
k = last;
}
sumflow += increase;
}
return sumflow;
}
int main(void) {
cin >> n >> m >> s >> t;
memset(capa, 0, sizeof(capa));
memset(flow, 0, sizeof(flow));
//memset(pre, -1, sizeof(pre)); //不能在主函数里面更新,因为这样就只更新了一次
int x, y;
int c;
for (int i=0; i < m; i ++) {
cin >> x >> y >> c;
capa[x][y] += c; //重边就累加c
}
cout << maxFlow(s, t);
return 0;
}
by cpchenpi @ 2024-09-03 21:07:46
你的 bfs
和 maxFlow
的返回值仍然是 int
,改为 long long
立即通过。