Cod sursa(job #2245856)

Utilizator SqueekDanielTodasca Daniel SqueekDaniel Data 26 septembrie 2018 01:03:16
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.51 kb
#include <bits/stdc++.h>

#define MaxN 105
#define inf  (int)(1e9)

std::ifstream InFile("harta.in");
std::ofstream OutFile("harta.out");

struct GraphStruct {
    int N;
    int Src, Dest;
    int GradExt[MaxN], GradInt[MaxN];
    int Capacity[2*MaxN][2*MaxN],
        Flow[2*MaxN][2*MaxN];
    GraphStruct() {Src = 0; Dest = 2*MaxN-1;}

    struct NodeStruct {
        std::list <int> ADC;
    }   Node[2*MaxN];

    inline int In(int x) {return x;}
    inline int Out(int x){return x+N;}
    inline void AddEdge(int x, int y) {
        Node[x].ADC.push_back(y);
        Node[y].ADC.push_back(x);
    }

    int Previous[2*MaxN];
    bool Seen[2*MaxN];
    bool BFSFlow() {
        for (int i=0; i<2*MaxN; i++)
            Previous[i] = Seen[i] = 0;

        std::queue <int> BFSQueue;
        BFSQueue.push(Src);
        Seen[Src] = 1;

        int Front;
        while(!BFSQueue.empty()) {
            Front = BFSQueue.front();
            BFSQueue.pop();

            for (auto Vecin:Node[Front].ADC)
                if (Vecin != Front && !Seen[Vecin] && Capacity[Front][Vecin] != Flow[Front][Vecin]) {
                    BFSQueue.push(Vecin);
                    Previous[Vecin] = Front;
                    Seen[Vecin] = 1;
                }
        }   return Seen[Dest];
    }

    void ComputeFlow() {
        while(BFSFlow()) {
            for (auto Vecin:Node[Dest].ADC)
                if (Seen[Vecin] && Capacity[Vecin][Dest] != Flow[Vecin][Dest]) {
                    int MinFlow = inf;
                    Previous[Dest] = Vecin;

                    int p = Dest;
                    while(p!=Src)
                        MinFlow = std::min(MinFlow, Capacity[Previous[p]][p] - Flow[Previous[p]][p]),
                        p = Previous[p];

                    p = Dest;
                    while(p!=Src)
                        Flow[Previous[p]][p] += MinFlow,
                        Flow[p][Previous[p]] -= MinFlow,
                        p = Previous[p];
                }
        }
    }

    void FindEdges() {

    }
}   Graph;  // Cu graful asta construim o retea; la un nod i de la 1...N asociem un nod de interior/exterior;
            // De la sursa->exterior, gradul exterior; exterior->interior, capacitate 1; interior->destinatie, gradul interior.
void Citire() {
    InFile >> Graph.N;

    for (int i=0, Ext, Int; i<Graph.N; i++)
        InFile >> Ext >> Int,
        Graph.Capacity[Graph.Src][Graph.In(i+1)] = Ext,
        Graph.Capacity[Graph.Out(i+1)][Graph.Dest] = Int,
        Graph.AddEdge(Graph.Src, Graph.In(i+1)),
        Graph.AddEdge(Graph.Out(i+1), Graph.Dest);
}
void Rezolvare() {
    for (int i=0, j; i<Graph.N; i++)
        for (j=Graph.N; j<2*Graph.N; j++)
            if (i != j-Graph.N)
                Graph.Capacity[i+1][j+1] = 1;

    for (int i=0, j; i<Graph.N; i++)
        for (j=Graph.N; j<2*Graph.N; j++)
            if(Graph.Capacity[i+1][j+1] | Graph.Capacity[j+1][i+1])
                Graph.AddEdge(i+1, j+1);

    Graph.ComputeFlow();

    std::vector <std::pair <int, int>> Sol;
    for (int i=0, j; i<Graph.N; i++)
        for (j=Graph.N; j<2*Graph.N; j++)
            if (i != j-Graph.N && Graph.Capacity[i+1][j+1] == Graph.Flow[i+1][j+1])
                Sol.push_back(std::make_pair(i+1, j-Graph.N+1));

    OutFile << Sol.size() << '\n';
    for (int i=0; i<Sol.size(); i++)
        OutFile << Sol[i].first << ' ' << Sol[i].second << '\n';
}

int main()
{
    Citire();
    Rezolvare();

    return 0;
}