Cod sursă (job #345564)

#include <stdio.h>
#include <string.h>
#include <limits.h>

#define NMAX 1000
#define MMAX 5000

typedef struct queue {
          int f, l;
          int a[NMAX + 1];
        }QUEUE;

typedef struct edge {
          short u, v;
          int c, f;
          short next;
        } EDGE;

EDGE e[2 * MMAX + 1];
short head[NMAX + 1];
int last;
short edgeto[NMAX + 1];
char visit[NMAX + 1];
short level[NMAX + 1];
QUEUE q;


int min2(int x, int y) {
  return (x > y) ? y : x;
}

void init(QUEUE* q) {
  q->f = 0;
  q->l = -1;
}

int empty(QUEUE* q) {
 return (q->l + 1 == q->f);
}

void enqueue(QUEUE* q, int x) {
  q->a[++q->l] = x;
}

int peek(QUEUE* q) {
  return q->a[q->f];
}

void dequeue(QUEUE* q) {
  q->f++;
}

void addEdge(short u, short v, int cap) {
  e[last].u = u;
  e[last].v = v;
  e[last].c = cap;
  e[last].f = 0;
  e[last].next = head[u];

  head[u] = last;
  last++;
}

int bfs(int s, short finish, int n) {
  short p, u, v;

  memset(edgeto, -1, sizeof(edgeto));
  memset(visit, 0, sizeof(visit));
  memset(level, -1, sizeof(level));

  init(&q);
  enqueue(&q, s);
  visit[s] = 1;
  level[s] = 0;
  while (!empty(&q)) {
    u = peek(&q);
    dequeue(&q);

    for (p = head[u]; p != -1; p = e[p].next) {
      v = e[p].v;
      if (visit[v] == 0 && e[p].f < e[p].c) {
        edgeto[v] = p;
        visit[v] = 1;
        level[v] = level[u] + 1;

        enqueue(&q, v);
      }
    }
  }

  return visit[finish];
}

int findflux(short start, short finish, int n) {
  short p, v, edgeidx;
  int flux, vmin;

  flux = 0;
  while (bfs(start, finish, n)) {
    for (p = head[finish]; p != -1; p = e[p].next) {
      v = e[p].v;
      if ((level[v] + 1 == level[finish]) && (e[p ^ 1].f < e[p ^ 1].c)) {
        edgeidx = p ^ 1;
        vmin = INT_MAX;
        while (edgeidx != -1) {
          vmin = min2(vmin, e[edgeidx].c - e[edgeidx].f);

          v = e[edgeidx].u;
          edgeidx = edgeto[v];
        }

        edgeidx = p ^ 1;
        while (edgeidx != -1) {
          e[edgeidx].f += vmin;
          e[edgeidx ^ 1].f -= vmin;

          v = e[edgeidx].u;
          edgeidx = edgeto[v];
        }

        flux += vmin;
      }
    }
  }

  return flux;
}

void findmincut(int n, FILE* fout) {
  int p, u, v;

  for (u = 1; u <= n; u++) {
    for (p = head[u]; p != -1; p = e[p].next) {
      v = e[p].v;
      if (visit[u] && !visit[v] && (0 < e[p].c) && (e[p].f == e[p].c)) {
         fprintf(fout, "%d %d\n", u, v);
      }
    }
  }
}


int main() {
  FILE *fin, *fout;
  int n, m, cap, i, flux;
  short u, v;

  fin = fopen("mincut.in", "r");
  fout = fopen("mincut.out", "w");

  memset(head, -1, sizeof(head));

  fscanf(fin, "%d %d", &n, &m);
  for (i = 0; i < m; i++) {
    fscanf(fin, "%hd %hd %d", &u, &v, &cap);

    addEdge(u, v, cap);
    addEdge(v, u, 0);
  }
  
  flux = findflux(1, n, n);

  fprintf(fout, "%d\n", flux);

  findmincut(n, fout);

  fclose(fin);
  fclose(fout);

  return 0;
}