Cod sursa(job #1998329)

Utilizator GoogalAbabei Daniel Googal Data 7 iulie 2017 14:57:27
Problema Taramul Nicaieri Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream in("harta.in");
ofstream out("harta.out");

const int NMAX = 2 * 100 + 20;
const int INF = 1 << 30;
const int DIM = 10000;

int n, m, src, dest;
int nin[1 + NMAX], nout[1 + NMAX];
int cap[1 + NMAX][1 + NMAX];
bool vis[1 + NMAX];
int p[1 + NMAX];
int a[1 + NMAX][1 + NMAX];
char buff[DIM];
int poz;

vector < int > g[1 + NMAX];

int read(){
  int x = 0;

  while(!isdigit(buff[poz]))
    if(++poz == DIM){
      in.read(buff,DIM);
      poz = 0;
    }

  while(isdigit(buff[poz])){
    x = x * 10 + (buff[poz] - '0');

    if(++poz == DIM){
      in.read(buff,DIM);
      poz = 0;
    }
  }

  return x;
}

void addedge(int i, int j, int fl){
  cap[i][j] = fl;
  g[i].push_back(j);
  g[j].push_back(i);
}

int trans(int x){
  if(n < x)
    return x - n;
  else
    return x + n;
}

bool bfs(){
  fill(vis, vis + NMAX, 0);
  fill(p, p + NMAX, 0);
  queue < int > q;
  q.push(src);
  while(!q.empty()){
    int from = q.front();
    q.pop();
    for(int i = 0; i < g[from].size(); i++){
      int to = g[from][i];
      if(vis[to] == false && cap[from][to] - a[from][to] > 0){
        q.push(to);
        vis[to] = 1;
        p[to] = from;
      }
    }
  }
  return vis[dest];
}

void updateg(){
  for(int i = 1; i <= n; i++){
    addedge(src, i, nout[i]);
    addedge(trans(i), dest, nin[i]);
  }

  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
      if(i != j){
        addedge(i, trans(j), 1);
        addedge(j, trans(i), 1);
      }
    }
  }
}

int solve(){
  int minn = INF;
  for(int i = dest; i != src; i = p[i])
    minn = min(minn, cap[p[i]][i] - a[p[i]][i]);
  for(int i = dest; i != src; i = p[i]){
    a[p[i]][i] += minn;
    a[i][p[i]] -= minn;
  }
  return minn;
}

void maxflow(){
  int answer = 0;
  while(bfs())
    answer += solve();
  out << answer << '\n';
  for(int i = 1; i <= n * 2; i++){
    for(int j = 1; j <= n * 2; j++){
      if(a[i][j] > 0){
        out << ((i > n) ? (i - n) : i) << ' ';
        out << ((j > n) ? (j - n) : j) << '\n';
      }
    }
  }
}

void getdata(){
  n = read();
  src = 0;
  dest = n * 2 + 1;
  for(int i = 1; i <= n; i++){
    nout[i] = read();
    nin[i] = read();
  }
}

int main()
{
  getdata();
  updateg();
  maxflow();
  return 0;
}