Cod sursa(job #3187984)

Utilizator Alexandru_IstrateIstrate Alexandru Alexandru_Istrate Data 31 decembrie 2023 19:22:36
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.42 kb
#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
#include <fstream>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
struct Edge{
    int destination;
    int capacity;
    int flow;
    int residual;

    Edge(int v, int c){
        destination = v;
        capacity = c;
        flow = 0;
        residual = capacity;
    }
};

class Graph{
int V;
vector< vector<Edge> > adj;

public:

Graph(const int& V){
    this->V = V;
    adj = vector< vector<Edge> >(V+2);
}

void AddEdge(const int& u, const int& v, const int& c){
    Edge e_u(v,c);
    Edge e_v(u,0);
    adj[u].push_back(e_u);
    adj[v].push_back(e_v);
}


int EdmondsKarp(int source, int sink) {
        int maxFlow = 0;

        while (true) {
            vector<int> parent(V+2, -1); 
            queue<pair<int, int>> q;    
            q.push({source, INT_MAX});

            while (!q.empty()) {
                int u = q.front().first;
                int minCapacity = q.front().second;
                q.pop();

                for (const Edge& e : adj[u]) {
                    int v = e.destination;
                    if (parent[v] == -1 && e.residual > 0) {
                        parent[v] = u;

                        // Actualizăm capacitatea minimă pe drum
                        int newMinCapacity = min(minCapacity, e.residual);
                        q.push({v, newMinCapacity});

                        if (v == sink) {
                            int pathFlow = newMinCapacity;
                            int current = v;

                            while (current != source) {
                                int previous = parent[current];
                                for (Edge& edge : adj[previous]) {
                                    if (edge.destination == current) {
                                        edge.residual -= pathFlow;
                                        edge.flow += pathFlow;
                                        break;
                                    }
                                }

                                for (Edge& reverseEdge : adj[current]) {
                                    if (reverseEdge.destination == previous) {
                                        reverseEdge.residual += pathFlow;
                                        break;
                                    }
                }
                                current = previous;
                            }

                            maxFlow += pathFlow;
                            break;
                        }
                    }
                }
            }

            if (parent[sink] == -1) {
                break;
            }
        }

        return maxFlow;
    }

void Afisare(){
    for(int i=0;i<=V+1;i++)
        for(auto e: adj[i])
            cout<<i<<" "<<e.destination<<" "<<e.capacity<<" "<<e.flow<<" "<<e.residual<<"\n";
}

void Roads(){
    for(int i=1;i<=V/2;i++){
        for(auto e : adj[i]){
            if(e.residual==0&&e.capacity)
                g<<i<<" "<<e.destination-V/2<<endl;

        }
        
    }
}
};




int main(){

    int N;
    f>>N;
    int source = 0;
    int sink = 2*N+1;
    Graph G(2*N);
    int out,in;
    for(int i=1; i<=N; i++){
        f>>out>>in;
        G.AddEdge(source,i,out);
        G.AddEdge(N+i,sink,in);
        for(int j=1;j<=N;j++)
            if(i!=j) G.AddEdge(i,N+j,1);
    }

g<<G.EdmondsKarp(source,sink)<<endl;
G.Roads();

    return 0;
}