Cod sursa(job #2961345)

Utilizator razvan1403razvan razvan1403 Data 6 ianuarie 2023 11:35:08
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul II Marime 2.76 kb
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define l long
#define d double
#define in int
#define si(x) scanf('%d', &x)
#define sl(x) scanf('%lld', &x)
#define ss(s) scanf('%s', s) 
#define pi(x) printf('%d', x)
#define pl(x) printf('%lld', x)
#define ps(s) printf('%s', s) 
#define pb push_back 
#define mp make_pair 
#define F first 
#define S second 
#define all(x) x.begin(), x.end() 
#define clr(x) memset(x, 0, sizeof(x))
#define sortall(x) sort(all(x)) 
typedef pair<int, int> pii; 
typedef pair<ll, ll> pl; 
typedef vector<int> vi; 
typedef vector<ll> vl; 
#define modulo 1000000007
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define inf INT_MAX
typedef vector<pii> vpii;

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

int n,m, x,y, fluxCurent, total;
int start, final;
vector<vector<int>>capacitate, flux;
vector<vector<int>> graf;
vector<int> vizitat, nod_flux;

void read(){
  fin>>n;
  start = 0;
  final = 2*n + 1;
  graf = vector<vector<int>>(final + 1);
  capacitate = vector<vector<int>>(final + 1, vector<int>(final + 1, 0));

  flux = vector<vector<int>>(final + 1, vector<int>(final + 1, 0));
  for(int i=1;i<=n;i++){
    fin>>x>>y;
    graf[start].push_back(i);
    graf[n + i].push_back(final);
    capacitate[start][i] = x;
    capacitate[n+i][final] = y;

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

  }
}

int bfs(){
  vizitat = vector<int>(final + 1, 0);
  queue<int> coada;
  coada.push(start);
  vizitat[start] = 1;
  while(!coada.empty()){
    int nodCurent = coada.front();
    coada.pop();
    for(int i=0;i<graf[nodCurent].size();i++){
      if(capacitate[nodCurent][graf[nodCurent][i]] > 0 && vizitat[graf[nodCurent][i]] == 0){
        nod_flux[graf[nodCurent][i]] = nodCurent;
        if(graf[nodCurent][i] == final)
          return 1;
        coada.push(graf[nodCurent][i]);
        vizitat[graf[nodCurent][i]] = 1;
      }
    }
  }
  return 0;
}

int main() 
{
  ios_base::sync_with_stdio(0), fin.tie(0), fout.tie(0);

  read();
  nod_flux = vector<int>(final + 1, -1);
  while(bfs()){
    fluxCurent = inf;
    for(int i = final;i!= start;i = nod_flux[i]){
      
      fluxCurent = min(fluxCurent, capacitate[nod_flux[i]][i]);
    }

    for(int i = final;i!= start;i = nod_flux[i]){
      
      capacitate[nod_flux[i]][i] -= fluxCurent;
      capacitate[i][nod_flux[i]] += fluxCurent;
    }
    total += fluxCurent;
  }

  fout<<total<<endl;
  for(int i=1;i<=n;i++){
    for(int j=0;j<graf[i].size();j++){
      if(capacitate[i][graf[i][j]] == 0 && graf[i][j] > n)
        fout<<i<<" "<<graf[i][j] - n<<endl;
    }
  }

  return 0;
}