striver-模板-dinic

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

#include <stdio.h>
int b[100000], link[100000], last[100000];
int e[100000], w[100000], tt[100000], next[100000], g[100000], now[100000], f[100000], ff[100000];
int flow, top = 1, n, m, st, sw;
int ans;
void connect(int j, int k, int l)
{
   top ++;  e[top] = k;  w[top] = l;
   tt[top]  =  j;
   next[top]  =  link[j];
   link[j] = top;
   top ++;  e[top] = j; w[top] = 0;
   tt[top] = k;
   next[top] = link[k];
   link[k] = top;
}
void readin()
{
   int j, k, l, i;
   scanf("%d%d", &n, &m);
   st = 1; sw = n;
   for (i = 1; i <= m; i++)
     {
       scanf("%d%d%d", &j, &k, &l);
       connect(j, k, l);
     }
}  
int bfs()
{
  int t, ww, q;
  for (t = 1; t <= sw; t ++) {
    f[t] = -1;
    now[t] = link[t];
    }
  t = 0; ww = 1;  b[ww] = st;
  f[st] = 1;
  while (t < ww) {
    t ++;  q = link[b[t]];
    while (q) {
      if (w[q] > 0 && f[e[q]] < 0) 
        {
          f[e[q]] = f[b[t]] + 1;
          if (e[q] == sw) return 1;
          ww ++; b[ww] = e[q];
        }
         q = next[q];
      }
   }
  return 0;
}
int min(int a, int b) { return (a > b ? b : a); }
void dinic()
{
   int i, q, t;
   i = st;     ff[st] = 10000000;
   while (f[st] != -1)   {
    q = now[i];
    while (q)  if (w[q] > 0 && f[e[q]] - 1 == f[i]) break;
               else q = next[q];
    if (q) {
     now[i] = q;  i = e[q]; g[e[q]] = q;
     ff[e[q]] = min(ff[tt[q]], w[q]);
     if (i == sw) {
         ans += ff[sw];
         while (i != st)
          {
           w[g[i]] -= ff[sw];
           w[g[i] ^ 1] += ff[sw];
           i = tt[g[i]];
          }
       }
   }
   else {
      f[i] = -1;
      i = tt[g[i]];
     }
   }
}
int main(){
  readin();
  ans = 0;
  while (bfs())  dinic();
  printf("%d\n", ans);
}

#include

int b[100000], link[100000], last[100000];

int e[100000], w[100000], tt[100000], next[100000], g[100000], now[100000], f[100000], ff[100000];

int flow, top = 1, n, m, st, sw;

int ans;

void connect(int j, int k, int l)

{

top ++; e[top] = k; w[top] = l;

tt[top] = j;

next[top] = link[j];

link[j] = top;

top ++; e[top] = j; w[top] = 0;

tt[top] = k;

next[top] = link[k];

link[k] = top;

}

void readin()

{

int j, k, l, i;

scanf("%d%d", &n, &m);

st = 1; sw = n;

for (i = 1; i <= m; i++)

{

scanf("%d%d%d", &j, &k, &l);

connect(j, k, l);

}

}

int bfs()

{

int t, ww, q;

for (t = 1; t <= sw; t ++) {

f[t] = -1;

now[t] = link[t];

}

t = 0; ww = 1; b[ww] = st;

f[st] = 1;

while (t < ww) {

t ++; q = link[b[t]];

while (q) {

if (w[q] > 0 && f[e[q]] < 0)

{

f[e[q]] = f[b[t]] + 1;

if (e[q] == sw) return 1;

ww ++; b[ww] = e[q];

}

q = next[q];

}

}

return 0;

}

int min(int a, int b) { return (a > b ? b : a); }

void dinic()

{

int i, q, t;

i = st; ff[st] = 10000000;

while (f[st] != -1) {

q = now[i];

while (q) if (w[q] > 0 && f[e[q]] - 1 == f[i]) break;

else q = next[q];

if (q) {

now[i] = q; i = e[q]; g[e[q]] = q;

ff[e[q]] = min(ff[tt[q]], w[q]);

if (i == sw) {

ans += ff[sw];

while (i != st)

{

w[g[i]] -= ff[sw];

w[g[i] ^ 1] += ff[sw];

i = tt[g[i]];

}

}

}

else {

f[i] = -1;

i = tt[g[i]];

}

}

}

int main(){

readin();

ans = 0;

while (bfs()) dinic();

printf("%d\n", ans);

}