网络最大流模板 EK算法 64分 求教

蒟蒻求教/kk 代码如下

#include<bits/stdc++.h>
using namespace std;

const long long  inf = 1 << 29, N = 2010, M = 20010;

long long head[N], ver[M], edge[M], Next[M], v[N], incf[N], pre[N];
long long n, m, s, t, tot = 1, maxflow;

void add(int x, int y, int z){
  ver[++tot] = y, edge[tot] = z, Next[tot] = head[x], head[x] = tot;
  ver[++tot] = x, edge[tot] = 0, Next[tot] = head[y], head[y] = tot;
}

bool bfs(){
  memset(v, 0, sizeof(v));
  queue<int> q;
  q.push(s);
  v[s] = 1;
  incf[s] = inf;
  while(q.size()){
    int x = q.front();
    q.pop();
    for(int i = head[x]; i; i = Next[i]){
      if(edge[i]){
        int y = ver[i];
        if(v[y]) continue;
        incf[y] = min(incf[x], edge[i]);
        pre[y] = i;
        q.push(y), v[y] = 1;
        if(y == t) return 1;
      }
    }
  }
  return 0;
}

void update(){
  int x = t;
  while(x != s){
    int i = pre[x];
    edge[i] -= incf[t];
    edge[i ^ 1] += incf[t];
    x = ver[i ^ 1];
  }
  maxflow += incf[t];
}

int main(){
  freopen("ek.in", "r", stdin);
  freopen("ek.out", "w", stdout);
  scanf("%d%d", &n, &m);
  scanf("%d%d", &s, &t);
  memset(head, 0, sizeof(head));
  for(int i = 1; i <= m; i++){
    int x, y, c;
    scanf("%d%d%d", &x, &y, &c);
    add(x, y, c);
  }
  while(bfs()) update();
  printf("%d\n", maxflow);
  return 0;
}

提交记录