Cod sursa(job #2960646)

Utilizator popashtefan10Popa Stefan popashtefan10 Data 4 ianuarie 2023 19:49:03
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.96 kb
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <fstream>

using namespace std;

class Flow {
  struct Edge {
    int from, to;
    int cf;

    Edge(int from = 0, int to = 0, int cf = 0) : from(from), to(to), cf(cf) {}
  };

  int n, m;
  int source, destination;
  // adjList[i] = indicii muchiilor care pornesc din nodul i
  vector<vector<int>> adjList;
  vector<Edge> edges;
  // dad[i] = indicele muchiei parinte din arborele BFS
  vector<int> dad;

  // adauga flux in drumul de ameliorare care se termina in nodul dat ca parametru si intoarce valoarea fluxului adaugat
  int addFlow(int node) {
    int canAdd = -1; // fluxul maxim pe care il pot adauga pe drumul de ameliorare curent
    int crt = node;
    while(crt != source) {
      if(canAdd == -1 || edges[dad[crt]].cf < canAdd)
        canAdd = edges[dad[crt]].cf;
      crt = edges[dad[crt]].from;
    }

    // parcurg din nou drumul de ameliorare ca sa adaug noul flux
    crt = node;
    while(crt != source) {
      edges[dad[crt]].cf -= canAdd;
      edges[dad[crt] ^ 1].cf += canAdd;
      crt = edges[dad[crt]].from;
    }

    return canAdd;
  }

  // creeaza arborele BFS prin vectorul de tati si intoarce daca a gasit macar un drum de ameliorare sau nu
  bool bfs() {
    bool reachedDestination = false; // daca am ajuns la destinatie printr-un drum de ameliorare
    queue<int> q;
    q.push(source);
    for(int i = 1; i <= n; i++)
      dad[i] = -1;

    while(!q.empty()) {
      int node = q.front();
      q.pop();

      for(int edgeIdx: adjList[node]) {
        int ngh = edges[edgeIdx].to;
        // caut muchii in care mai pot adauga flux si care ajung in noduri nevizitate
        if(ngh == source || dad[ngh] != -1 || edges[edgeIdx].cf == 0)
          continue;
        // daca am ajuns la destinatie nu memorez nodul din care am ajuns pentru ca pot avea mai multe drumuri
        if(ngh == destination) {
          reachedDestination = true;
          continue;
        }

        dad[ngh] = edgeIdx;
        q.push(ngh);
      }
    }

    return reachedDestination;
  }

public:
  void init(int n, int source = 1, int destination = -1) {
    this->n = n;
    this->source = source;
    this->destination = destination == -1 ? n : destination;
    adjList.resize(n + 1);
    dad.resize(n + 1);
  }

  // adauga muchia (from, to) in retea; indicele muchiei va fi pe o pozitie para, iar muchia inversa va fi pe urmatoarea pozitie
  void addEdge(int from, int to, int capacity) {
    edges.push_back(Edge(from, to, capacity));
    adjList[from].push_back(edges.size() - 1);
    // adaug si muchia inversa de capacitate 0
    edges.push_back(Edge(to, from, 0));
    adjList[to].push_back(edges.size() - 1);
  }

  // intoarce fluxul maxim din retea
  int maxFlow() {
    int maxFlow = 0;

    // cat timp exista drumuri de ameliorare mai putem adauga flux
    while(bfs())
      for(int edgeIdx: adjList[destination]) {
        int node = edges[edgeIdx].to;

        // conectam pe rand nodul destinatie la toate nodurile din care se poate ajunge in acesta si care sunt capatul unui drum de ameliorare
        if((node == source || dad[node] != -1) && edges[edgeIdx ^ 1].cf > 0) {
          dad[destination] = edgeIdx ^ 1;
          maxFlow += addFlow(destination);
        }
      }

    return maxFlow;
  }

  vector<pair<int, int>> getEdges() {
    vector<pair<int, int>> ret;

    for(int i = 0; i < edges.size(); i += 2)
      if(edges[i].cf == 0 && edges[i].from != source && edges[i].to != destination)
        ret.push_back({ edges[i].from, edges[i].to });

    return ret;
  }
};

int n;

void read(Flow &flow) {
  ifstream fin("harta.in");
  int in, out, source, destination;

  fin >> n;
  source = 0;
  destination = 2 * n + 1;
  flow.init(2 * n + 2, source, destination);
  for(int i = 1; i <= n; i++) {
    fin >> out >> in;
    // adaug muchii de la sursa la fiecare nod cu capacitatea egala cu gradul de iesire,
    // intrucat cantitatea de flux care va iesi din nod este data de numarul de muchii care ies din el
    flow.addEdge(source, i, out);
    // adaug muchii de la fiecare nod la destinatie cu capacitatea egala cu gradul de intrare
    // intrucat cantitatea de flux care intra in nod este data de numarul de muchii care intra in el
    flow.addEdge(n + i, destination, in);
  }
  // adaug muchii intre fiecare 2 noduri diferite de capacitate 1
  // dintre aceste muchii vor fi selectate cele prin care va trece flux
  for(int i = 1; i <= n; i++)
    for(int j = 1; j <= n; j++)
      if(i != j)
        flow.addEdge(i, n + j, 1);
}

int main() {
  Flow flow;

  read(flow);
  int edgesCount = flow.maxFlow();
  ofstream fout("harta.out");
  fout << edgesCount << '\n';

  vector<pair<int, int>> edges = flow.getEdges();
  for(pair<int, int> edge: edges)
    fout << edge.first << ' ' << (edge.second > n ? edge.second - n : edge.second) << '\n';

  return 0;
}