Cod sursa(job #2961910)

Utilizator NicuDirvaDirva Nicolae NicuDirva Data 7 ianuarie 2023 13:09:48
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.02 kb
#include <fstream>
#include <cstring>
#include <queue>

#define NRMAX 210

/**
-Construim un graf bipartit cu cele n noduri in ambele parti si vom adauga
o sursa si o destinatie. Costurile vor fi: muchie in graf bipartit - cost 1, muchie de la sursa la stanga - cost de intrare,
muchie de la dreapta la destinatie - cost de iesire

Daca suma gradelor de intrare difera de suma gradelor de iesire sau daca suma nu este egala cu fluxul maxim gasit inseamna ca nu avem solutie.
*/

using namespace std;

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



int n,m,dad[NRMAX],total_in,total_out;
int capacitate[NRMAX][NRMAX];
bool viz[NRMAX],in_queue[NRMAX];

int BF()
{
    queue<int> q;
    q.push(0);
    dad[0] = -1;
    in_queue[0] = 1;

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

        if(viz[node]==1)
            continue;
        viz[node] = 1;

        for(int i=0;i<=m;++i)
            if(capacitate[node][i] > 0 )
                if(in_queue[i]==0)
                {
                    in_queue[i] = 1;
                    dad[i] = node;
                    q.push(i);
                }
    }

    if(viz[m])
        return 1;
    return 0;
}

int main()
{
    fin>>n; m=2*n+1;
    for(int i=1;i<=n;++i)
    {
        int a,b;
        fin>>a>>b;
        capacitate[0][i] = a;
        capacitate[n+i][m] = b;
        total_in += a;
        total_out += b;
    }
    for(int i=1;i<=n;++i)
        for(int j=n+1;j<m;++j)
            if(i != j-n)
                capacitate[i][j] = 1;
    while(BF())
    {
        for(int i=n+1;i<m;++i)
            if(capacitate[i][m] && viz[i])
            {
                int actual_flow = capacitate[i][m], node = i;

                while(node != 0)
                {
                    actual_flow = min(actual_flow,capacitate[dad[node]][node]);
                    node = dad[node];
                }

                node = i , capacitate[node][m] -= actual_flow;

                while(node != 0)
                {
                    capacitate[dad[node]][node] -= actual_flow;
                    capacitate[node][dad[node]] += actual_flow;
                    node = dad[node];
                }
            }

        memset(dad,0,sizeof(dad));
        memset(viz,0,sizeof(viz));
        memset(in_queue,0,sizeof(in_queue));
    }

    queue<pair<int,int> > edges;

    for(int i=1;i<=n;++i)
        for(int j=n+1;j<m;++j)
            if(capacitate[j][i] > 0)
                edges.push(make_pair(i,j-n));

    int nr_edges = edges.size();

    if(total_in != total_out || total_in != nr_edges)
    {
        fout<<"-1"<<"\n";
        return 0;
    }

    fout<<nr_edges<<"\n";

    while(edges.size())
    {
        int a = edges.front().first;
        int b = edges.front().second;
        edges.pop();
        fout<<a<<" "<<b<<"\n";
    }

    fin.close();
    fout.close();

    //Complexitate: O(n*m^2), n = numar de varfuri, m = numar de muchii
    return 0;
}