2946880_ac_0ms_508k.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int mx = 300;
const int inf = (int)1e9;

int N, M, S, T, L, R, c[mx][mx], d[mx], op[mx], st[mx], lst[mx], tp, maxflow;

int init();
int calc();
void flow();

int main()
{
  while(init()) {
    while(calc()) flow();
    printf("%d\n", maxflow);
  }
  return 0;
}

int init()
{
  int x, y, t;

  if(2 != scanf("%d%d", &M, &N)) return 0;
  fill_n(c[0], mx * mx, 0);
  for(int i = 0; i < M; i++) {
    scanf("%d%d%d", &x, &y, &t);
	if(x!=y)
		c[--x][--y] += t;
  }
  S = 0; T = N - 1;
  maxflow = 0;
  return 1;
}

int calc()
{
  fill_n(d, mx, 0);
  d[op[0] = S] = 1;
  st[1] = 1;

  for(L = 0, R = 1; L < R; L++)
    for(int i = 0; i < N; i++) 
      if(c[op[L]][i] && !d[i]) {
    d[op[R++] = i] = d[op[L]] + 1;
    st[d[i]] = R;
      }
  return d[T];
}

int fnext(int u)
{
  if(d[u] == d[op[R - 1]]) return -1;
  for(int i = st[d[u]]; i < st[d[u] + 1]; i++) if(d[op[i]] > 0 && c[u][op[i]]) return op[i];
  return -1;
}

int refresh(int& tp)
{
  int ret(inf), top(tp);
  for(int i = top - 1; i; i--) 
  {
	  if(c[lst[i-1]][lst[i]]<ret)
		  ret = c[lst[i - 1]][lst[i]];
  }
  for(i = top - 1; i; i--) {
    c[lst[i]][lst[i - 1]] += ret;
    if(!(c[lst[i - 1]][lst[i]] -= ret)) tp = i - 1;
  }
  return ret;
}

void flow()
{
  for(tp = 1, lst[0] = S; tp; ) 
    if(lst[tp - 1] == T) maxflow += refresh(tp);
    else {
      lst[tp] = fnext(lst[tp - 1]);
      if(lst[tp] >= 0) tp++;
      else d[lst[--tp]] = -10;
    }
}