rt bfs进去第二次h[4]就等于0了,
我就很纳闷,我都没修改他呀 然后后面就没法正常走了 给出样例‘
4 5 4 3
4 2 30
4 3 20
2 3 20
2 1 30
1 3 30
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int M = 10005;
const int N = 5005;
int n, m, s, t;
struct node {
ll v, c, next;
} e[M];
int h[M], cur[N], d[N];;
int a, b, c, idx=0;
inline int read() {
int s = 0;
char ch = getchar();
while (ch >= '0' && ch <= '9') {
s = s * 10 + ch - '0';
ch = getchar();
}
return s;
}
bool bfs() {
//cout<<"sss";
queue<int>q;
memset(d, 0, sizeof d);
q.push(s);
d[s] = 1;
while (q.size()) {
int u = q.front();
q.pop();
cout<<u<<" ";
cout<<h[u]<<endl;
for (int i = h[u]; i; i = e[i].next) {
int v = e[i].v;
if (d[v] == 0 && e[i].c) {
d[v] = d[u] + 1;
q.push(v);
if (v == t)return true;
}
}
}
return false ;
}
ll dfs( int u, ll mf) {
if (u == t)return mf;
ll sum = 0;
for (int i = cur[u]; i; i = e[i].next) {
int v = e[i].v;
if (d[v] == d[u] + 1 && e[i].c) {
cur[u] = i;
ll f = dfs(v, min(e[i].c, mf));
sum += f;
e[i].c -= f;
e[i ^ 1].c += f;
mf -= f;
if (mf == 0)break;
}
}
if (sum == 0)d[u] = 0;
return sum;
}
ll dinic() {
ll flow = 0;
while (bfs()) {
memcpy(cur, h, sizeof h);
flow += dfs(s, 1e9);
}
return flow;
}
int main() {
n = read(), m = read();
s = read(), t = read();
memset(h,0,sizeof h);
for (int i = 1; i <= m; i++) {
a = read(), b = read(), c = read();
e[++idx] = {b, c, h[a]};
h[a] = idx;
e[++idx]={a,0,h[b]};
h[b]=idx;
}
cout << dinic();
return 0;
}