Cod sursa(job #579969)

Utilizator dushmiMihai-Alexandru Dusmanu dushmi Data 12 aprilie 2011 17:01:51
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.16 kb
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

const int N = 210;

int S, D, n, t[N], cap[N][N], flux[N][N];

bool viz[N];

queue<int> Q;

vector<int> v[N];

void read() {
  int x, y, nrm = 0;
  freopen("harta.in", "r", stdin);
  freopen("harta.out", "w", stdout);
  scanf("%d", &n);
  for (int i = 1; i <= n; ++ i) {
    scanf("%d %d", &x, &y);
    nrm += x;
    cap[0][i] = x;
    cap[n + i][2 * n + 1] = y;
  }
  printf("%d\n", nrm);
}

void init() {
  S = 0;
  D = 2 * n + 1;
  
  for (int j = 1; j <= n; ++ j) {
    v[S].push_back(j);
    v[j].push_back(S);
  }

  for (int i = 1; i <= n; ++ i) {
    v[n + i].push_back(D);
    v[D].push_back(n + i);
  }

  for (int i = 1; i <= n; ++ i) 
    for (int j = 1; j <= n; ++ j)
      if (i != j) {
        v[i].push_back(n + j);
        v[n + j].push_back(i);
        cap[i][n + j] = 1;
      }
}

int min(int x, int y) {
  return x < y ? x : y;
}

int calculeaza(int nod) {
  int rez = 2000000000;
  for (int i = nod; i; i = t[i])
    rez = min(rez, cap[t[i]][i] - flux[t[i]][i]);
  return rez;
}

void propaga(int nod, int fl) {
  for (int i = nod; i; i = t[i]) {
    flux[t[i]][i] += fl;
    flux[i][t[i]] -= fl;
  }
}

bool BFS() {
  int nc;
  viz[S] = 1;
  Q.push(S);

  while (! Q.empty()) {
    nc = Q.front();
    Q.pop();
    if (nc == D)
      continue;

    for (vector <int> :: iterator it = v[nc].begin(); it != v[nc].end(); ++ it)
      if (! viz[*it] && flux[nc][*it] < cap[nc][*it]) {
        viz[*it] = 1;
        t[*it] = nc;
        Q.push(*it);
      }
  }

  return viz[D];
}

void reset() {
  for (int i = S; i <= D; ++ i) {
    t[i] = 0;
    viz[i] = 0;
  }
}

void maxflow() {
  int minf;
  
  while (BFS()) {
    for (vector <int> :: iterator it = v[D].begin(); it != v[D].end(); ++ it)
      if (viz[*it]) {
        minf = min(cap[*it][D] - flux[*it][D], calculeaza(*it));
        flux[*it][D] += minf;
        flux[D][*it] -= minf;
        propaga(*it, minf);
      }
    reset();
  }
}

void afis() {
  for (int i = 1; i <= n; ++ i)
    for (int j = 1; j <= n; ++ j)
      if (flux[i][n + j] == 1)
        printf("%d %d\n", i, j);
}

int main() {
  read();
  init();
  maxflow();
  afis();
  return 0;
}