Cod sursa(job #1790712)

Utilizator cella.florescuCella Florescu cella.florescu Data 28 octombrie 2016 17:23:52
Problema Taramul Nicaieri Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <fstream>
#include <cstring>

using namespace std;

#include <queue>
#include <vector>

const int MAXN = 100;
const int MAXNODES = 2 * MAXN + 2;
const int INF = 5318008;

int seen[MAXNODES + 1], cap[MAXNODES + 1][MAXNODES + 1], flow[MAXNODES + 1][MAXNODES + 1], daddy[MAXNODES + 1];
vector <int> g[MAXNODES + 1];
queue <int> q;

int bfs(int n) {
  memset(seen, 0, sizeof(seen));
  int node;
  seen[0] = 1;
  q.push(0);
  while (q.empty() == 0) {
    node = q.front();
    if (node != n)
      for (int it : g[node])
        if (seen[it] == 0 && flow[node][it] < cap[node][it]) {
          seen[it] = 1;
          daddy[it] = node;
          q.push(it);
        }
    q.pop();
  }
  return seen[n];
}

inline int minim(int A, int B) {
  if (A < B)
    return A;
  return B;
}

int maxflow(int n) {
  int node, maxfl = 0, fl;
  while (bfs(n)) {
    for (auto it : g[n])
      if (seen[it] && flow[it][n] < cap[it][n]) {
        for (node = n, fl = INF, daddy[n] = it; node > 0; node = daddy[node])
          fl = minim(fl, cap[daddy[node]][node] - flow[daddy[node]][node]);
        for (node = n; node > 0; node = daddy[node]) {
          flow[daddy[node]][node] += fl;
          flow[node][daddy[node]] -= fl;
        }
        maxfl += fl;
      }
  }
  return maxfl;
}

struct Node {
  int gin, gout;
} v[MAXN + 1];

int main()
{
    int n, i, s, d, j, maxfl;
    ifstream fin("harta.in");
    fin >> n;
    for (i = 1; i <= n; ++i)
      fin >> v[i].gin >> v[i].gout;
    fin.close();
    s = 0; d = 2 * n + 1;
    for (i = 1; i <= n; ++i) {
      g[s].push_back(i); g[i + n].push_back(d);
      g[i].push_back(s); g[d].push_back(i + n);
      cap[s][i] = v[i].gin; cap[i + n][d] = v[i].gout;
      for (j = 1; j <= n; ++j)
        if (i != j) {
          cap[i][j + n] = INF;
          g[i].push_back(j + n);
          g[j + n].push_back(i);
        }
    }
    maxfl = maxflow(d);
    ofstream fout("harta.out");
    fout << maxfl << '\n';
    for (i = 1; i <= n; ++i)
      for (j = n + 1; j <= 2 * n; ++j)
        while (flow[i][j] > 0) {
          fout << i << " " << j - n << '\n';
          --flow[i][j];
        }
    fout.close();
    return 0;
}