Cod sursa(job #2109670)

Utilizator DruffbaumPopescu Vlad Druffbaum Data 20 ianuarie 2018 00:15:14
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.01 kb
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>

const int INF = 2e9;
const int MAXN = 1e2;

std::vector <int> g[2 * MAXN + 1];        
int flow[2 * MAXN + 1][2 * MAXN + 1], cap[2 * MAXN + 1][2 * MAXN + 1],
    fath[2 * MAXN + 1];
bool vis[2 * MAXN + 1];
std::queue <int> q;

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

bool bfs(int n) {
  int u;
  memset(vis, 0x00, sizeof(vis));
  vis[0] = 1;
  q.push(0);
  while (!q.empty()) {
    u = q.front();
    if (u != n) {
      for (auto v: g[u]) {
        if (!vis[v] && flow[u][v] < cap[u][v]) {
          vis[v] = 1;
          fath[v] = u;
          q.push(v);
        }
      }
    }
    q.pop();
  }
  return vis[n];
}

int main() {
  int n, u, v, in, out, s, d, fl, maxfl;
  FILE *f = fopen("harta.in", "r");
  fscanf(f, "%d", &n);
  s = 0;
  d = 2 * n + 1;
  for (int i = 1; i <= n; ++i) {
    fscanf(f, "%d%d", &in, &out);
    g[s].push_back(i);
    g[i].push_back(s);
    cap[s][i] = in;
    g[d].push_back(i + n);
    g[i + n].push_back(d);
    cap[i + n][d] = out;
    for (int j = 1; j <= n; ++j) {
      if (i ^ j) {
        g[i].push_back(j + n);
        g[j + n].push_back(i);
        cap[i][j + n] = 1;
      }
    }
  }
  fclose(f);
  maxfl = 0;
  while (bfs(d)) {
    for (auto u: g[d]) {
      if (vis[u] && flow[u][d] < cap[u][d]) {
        fath[d] = u;
        fl = INF;
        v = d;
        while (v > 0) {
          fl = min(fl, cap[fath[v]][v] - flow[fath[v]][v]);
          v = fath[v];
        }
        v = d;
        while (v > 0) {
          flow[fath[v]][v] += fl;
          flow[v][fath[v]] -= fl;
          v = fath[v];
        }
        maxfl += fl;
      }
    }
  }
  f = fopen("harta.out", "w");
  fprintf(f, "%d\n", maxfl);
  for (int i = 1; i <= n; ++i) {
    for (int j = n + 1; j <= 2 * n; ++j) {
      while (flow[i][j] > 0) {
        fprintf(f, "%d %d\n", i, j - n);
        --flow[i][j];
      }
    }
  }
  fclose(f);
  return 0;
}