Cod sursa(job #2594699)

Utilizator popashtefan10Popa Stefan popashtefan10 Data 6 aprilie 2020 15:34:25
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.67 kb
#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

const int NMAX = 100;
const int INF = 1000000000;

bool uz[2 * NMAX + 5];
int n, s, t, nrm;
int from[2 * NMAX + 5];
int cf[2 * NMAX + 5][2 * NMAX + 5];
queue<int> q;

bool bfs(int start) {
  for(int i = s; i <= t; i++)
    uz[i] = false;
  q.push(start);
  uz[start] = true;
  from[start] = -1;

  while(!q.empty()) {
    int nod = q.front();
    q.pop();
    if(nod == t)
      continue;

    for(int i = s; i <= t; i++)
      if(!uz[i] && cf[nod][i] > 0) {
        from[i] = nod;
        q.push(i);
        uz[i] = true;
      }
  }

  return uz[t];
}

void update_flux() {
  int minf = INF;
  for(int i = t; from[i] != -1; i = from[i])
    minf = min(minf, cf[from[i]][i]);
  if(minf == 0)
    return;

  for(int i = t; from[i] != -1; i = from[i]) {
    cf[from[i]][i] -= minf;
    cf[i][from[i]] += minf;
  }
}

void flux() {
  while(bfs(s))
    for(int i = n + 1; i <= 2 * n; i++)
      if(uz[i] && cf[i][t]) {
        from[t] = i;
        update_flux();
      }
}

int main() {
  freopen("harta.in", "r", stdin);
  freopen("harta.out", "w", stdout);
  int x, y;

  scanf("%d", &n);
  s = 0;
  t = 2 * n + 1;
  for(int i = 1; i <= n; i++) {
    scanf("%d %d", &x, &y);
    nrm += x;
    cf[s][i] += x;
    cf[n + i][t] += y;
  }

  for(int i = 1; i <= n; i++)
    for(int j = n + 1; j <= 2 * n; j++)
      if(i != j - n)
        cf[i][j] = 1;

  flux();

  printf("%d\n", nrm);
  for(int i = 1; i <= n; i++)
    for(int j = n + 1; j <= 2 * n; j++)
      if(i != j - n && cf[i][j] == 0)
        printf("%d %d\n", i, j - n);

  return 0;
}