Cod sursa(job #2956313)

Utilizator andlftLefter Andrei andlft Data 19 decembrie 2022 01:25:41
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.76 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

class Graph
{
private:
    vector<int> parent;
    vector<bool> seen;
    vector<vector<int>> capacityFromXtoY;
    int noOfVerticesInFirstSet;
    int noOfVertices;
    int lastVertex;
    int maxFlow;

public:
    Graph(int n, int n1)
    {
        noOfVertices = n+1;
        lastVertex = n+1;
        noOfVerticesInFirstSet = n1;
        capacityFromXtoY.resize(n+2);
        for (int i = 0; i <= n+1; i++)
        {
            capacityFromXtoY[i].resize(n+2, 0);
        }
        parent.resize(n+1, 0);
        seen.resize(n+1, 0);
        maxFlow = 0;
    }

    void readEdges()
    {
        for(int i = 1; i <= noOfVerticesInFirstSet; i++)
        {

            int n, m;
            fin >> n >> m;
            capacityFromXtoY[0][i] = n;
            capacityFromXtoY[noOfVerticesInFirstSet + i][lastVertex] = m;
            for (int j = noOfVerticesInFirstSet+1; j < noOfVertices; j++)
            {
                if(i != j-noOfVerticesInFirstSet)
                {
                    capacityFromXtoY[i][j] = 1;
                }
            }
        }
    }


    bool bfs()
    {
        seen.assign(noOfVertices + 2, 0);
        parent.assign(noOfVertices + 2, 0);
        queue<int> que;
        que.push(0);
        seen[0] = true;
        parent[0] = 0;
        while (!que.empty())
        {
            int front = que.front();
            que.pop();
            if(front != lastVertex)
            {
                for(int i = 1; i <= noOfVertices; i++)
                {
                    if(seen[i] == false && capacityFromXtoY[front][i] > 0)
                    {
                        que.push(i);
                        parent[i] = front;
                        seen[i] = true;
                    }
                }
            }
        }
        return seen[lastVertex];
    }

    void getMaxFlow()
    {
        while (this->bfs())
        {
            for(int i = noOfVerticesInFirstSet + 1 ; i < noOfVertices; i++)
            {
                if(seen[i] && capacityFromXtoY[i][lastVertex]>0)
                {
                    parent[lastVertex] = i;
                    int localMaxFlow = 1<<30;
                    int vrtx = lastVertex;
                    while(vrtx != 0)
                    {
                        localMaxFlow = min(localMaxFlow, capacityFromXtoY[parent[vrtx]][vrtx]);
                        vrtx = parent[vrtx];
                    }
                    if(localMaxFlow == 0)
                    {
                        continue;
                    }
                    vrtx = lastVertex;
                    while(vrtx != 0)
                    {
                        capacityFromXtoY[parent[vrtx]][vrtx] -= localMaxFlow;
                        capacityFromXtoY[vrtx][parent[vrtx]] += localMaxFlow;
                        vrtx = parent[vrtx];
                    }
                   maxFlow += localMaxFlow;


                }
            }
        }

//        return maxFlow;
          fout<<maxFlow<<"\n";
    }
    void output()
    {
        for(int i = 1; i <= noOfVerticesInFirstSet; i++)
        {
            for(int j = noOfVerticesInFirstSet+1; j < noOfVertices; j++)
            {
                if(capacityFromXtoY[i][j] == 0 && i != j - noOfVerticesInFirstSet)
                {
                    fout<<i<<" "<< j - noOfVerticesInFirstSet<<"\n";
                }
            }
        }
    }

};

int main()
{
    int n;
    fin>>n;
    Graph graph (n*2, n);
    graph.readEdges();
    graph.getMaxFlow();
    graph.output();
    return 0;
}