Cod sursa(job #3193837)

Utilizator euyoTukanul euyo Data 15 ianuarie 2024 20:18:52
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.55 kb
#include <bits/stdc++.h>

using namespace std;

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

const int DIM = 205;
const int INF = 1e9;

vector<int> G[DIM];
int cap[DIM][DIM];
int flow[DIM][DIM];
int viz[DIM];

void push_edge( int u, int v, int c ) {
  if ( c == 0 ) return;
  G[u].push_back(v);
  G[v].push_back(u);
  cap[u][v] += c;
}

int prv[DIM];
 
int bfs( int s, int d ) {
  queue<int> q;
  q.push(s);
  prv[s] = 0;
  while ( !q.empty() ) {
	int u = q.front();
	q.pop();
	for ( auto v : G[u] ) {
      if ( prv[v] == -1 && cap[u][v] > flow[u][v] ) {
        prv[v] = u;
		q.push(v);
	  }
	}
  }
  return prv[d];
}
 
int main() {
  int n, in, out;
  int s, d;

  fin >> n;
  s = 0, d = 2 * n + 1;
  for ( int i = 1; i <= n; ++i ) {
	fin >> out >> in;
    push_edge(s, i, out);
	push_edge(i + n, d, in);
  }
  for ( int i = 1; i <= n; ++i ) {
	for ( int j = 1; j <= n; ++j ) {
	  if ( i != j ) {
		push_edge(i, j + n, 1);
	  }
	}
  }
  int res = 0;
  while ( bfs(s, d) != -1 ) {
	int win = INF;
	for ( int u = d; u != s; u = prv[u] ) {
	  win = min(win, cap[prv[u]][u] - flow[prv[u]][u]);
	}
    for ( int u = d; u != s; u = prv[u] ) {
	  flow[prv[u]][u] += win;
	  flow[u][prv[u]] -= win;
	}
	res += win;
	for ( int i = s; i <= d; ++i ) {
	  prv[i] = -1;
	}
  }
  fout << res << "\n";
  vector<pair<int, int>> edges;
  for ( int i = 1; i <= n; ++i ) {
	for ( int j = 1; j <= n; ++j ) {
	  if ( flow[i][j + n] == 1 ) {
		edges.push_back({i, j});
	  }
	}
  }
  for ( auto [u, v] : edges ) {
	fout << u << " " << v << "\n";
  }
  fin.close();
  fout.close();
  return 0;
}