rt,一个当前弧优化写错了的代码怎么过的?
# include <bits/stdc++.h>
# define int long long
using namespace std;
const int N = 800 , INF = 1e18;
int n , m , cur = 1 , s , t , pre[N << 5] , nxt[N << 5] , head[N << 5] , edge[N << 5] , to[N << 5] , ceng[N << 5] , maxflow , tmp[N << 5];
void addedge (int u , int v , int w) {nxt[++cur] = head[u] , edge[cur] = w , to[cur] = v , head[u] = cur;}
bool bfs () {
memset (ceng , 0 , sizeof ceng);
queue <int> q;
q.push (s) , ceng[s] = 1;
while (!q.empty()) {
int now = q.front();
q.pop();
tmp[now] = head[now];//部分节点可能在此不会被更新tmp[now],导致我最大流的图用了一部分上次的残留下来的图
for (int i = head[now];i ;i = nxt[i]) {
int y = to[i];
if (edge[i] && !ceng[y]) {
ceng[y] = ceng[now] + 1 , q.push (y);
if (y == t) return 1;
}
}
}
return 0;
}
int dinic (int now , int flow) {
if (now == t) return flow;
int rest = flow;
for (int i = tmp[now] ; i && rest; i = nxt[i]) {
int y = to[i];
tmp[now] = i;
if (ceng[y] == ceng[now] + 1 && edge[i]) {
int inc = dinic (y , min(rest , edge[i]));
if (inc == 0) ceng[y] = 0;
edge[i] -= inc , edge[i ^ 1] += inc , rest -= inc;
}
}
return flow - rest;
}
signed main () {
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
memset (head , 0 , sizeof head);
cin >> n >> m >> s >> t;
for (int i = 1;i <= m;++i) {
int u , v , w;
cin >> u >> v >> w;
addedge (u , v , w);
addedge (v , u , 0);
}
while (bfs()) maxflow += dinic (s , INF);
cout << maxflow << '\n';
return 0;
}
至于hack,把 P2598 的后四个点建模之后的图拿过来就行了。