Cod sursa(job #2966956)

Utilizator mbrianaMerealbe Cris-Briana mbriana Data 18 ianuarie 2023 19:47:36
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.42 kb
//Ford Fulkerson Algorithm Edmonds Karp Algorithm For Max Flow
//O(VE^2)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");

int N, source, sink, maxflow;
vector<vector <int>> graph;
vector<bool> visited;
vector<int> parent;

vector<vector<int>> capacity;

bool bfs () {

    fill(visited.begin(), visited.end(), false);
    queue<int> q;
    visited[source] = true;
    parent[source] = -1;

    q.push(source);

    while (!q.empty()) {

        int nod_curent = q.front();
        q.pop();

        for (auto i: graph[nod_curent]) {

            if (!visited[i] && capacity[nod_curent][i]) {
                parent[i] = nod_curent;
                if (i == sink){
                    return true;
                }
                visited[i] = true;
                q.push(i);

            }
        }
    }
    return false;
}
int getMaxFlow(){
  while(bfs()){
      int minflow = 1e9;
      int aux = sink;
      while(aux)
      {
          minflow = min(capacity[parent[aux]][aux], minflow);
          aux = parent[aux];
      }
      aux = sink;
      while(aux)
      {
          capacity[parent[aux]][aux] -= minflow;
          capacity[aux][parent[aux]] += minflow;
          aux = parent[aux];
      }
      maxflow += minflow;
  }
    return maxflow;
}

int main ()
{
    f>>N;
    source = 0;
    sink = 2*N+1;
    graph.resize(sink+1);
    visited.resize(sink+1);
    capacity.resize(sink+1, vector<int>(sink+1, 0));
    parent.resize(sink+1,-1);

    for (int i=1; i<=N; i++)
        for (int j =1+N; j<=2*N; j++) {
            if (i != j-N)
            {
                graph[i].push_back(j);
                graph[j].push_back(i);

                graph[source].push_back(i);
                graph[i].push_back(source);

                graph[sink].push_back(i+N);
                graph[i+N].push_back(sink);

                capacity[i][j] = 1;

            }
        }

    for (int i=1; i<=N; i++) {
        int val1, val2;

        f >> val1 >> val2;

        capacity[source][i] = val1;
        capacity[i+N][sink] = val2;
    }

    g << getMaxFlow() << "\n";
    for (int i=1; i<=N; i++)
        for (int j=1+N; j<=2*N; j++){
            if (capacity[j][i]) {
                g << i << " " << j - N << "\n";
            }
        }


    return 0;
}