Cod sursa(job #1998337)

Utilizator GoogalAbabei Daniel Googal Data 7 iulie 2017 15:10:25
Problema Taramul Nicaieri Scor 95
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <algorithm>
#include <iostream>
#include <vector>
#include <cstdio>
#include <queue>

using namespace std;

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

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];

vector < int > g[1 + NMAX];

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(){
  freopen("harta.out", "w", stdout);
  int answer = 0;
  while(bfs())
    answer += solve();
  printf("%d\n", answer);
  for(int i = 1; i <= n * 2; i++){
    for(int j = 1; j <= n * 2; j++){
      if(a[i][j] > 0){
        int x = (i > n) ? (i - n) : i;
        printf("%d ", x);
        x = (j > n) ? (j - n) : j;
        printf("%d\n", x);
      }
    }
  }
}

void read(){
  freopen("harta.in", "r", stdin);

  scanf("%d", &n);
  src = 0;
  dest = n * 2 + 1;
  for(int i = 1; i <= n; i++)
    scanf("%d%d", &nout[i], &nin[i]);
}

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