Cod sursa(job #2958091)

Utilizator maria.neagaNeaga-Budoiu Maria maria.neaga Data 24 decembrie 2022 16:31:30
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.1 kb
#include <iostream>
#include <fstream>
#include <math.h>
#include <queue>

#define MAX 110000

using namespace std;
//Idee: dublez toate nodurile din graf

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

int n, grInt, grExt; //gradul interior si exterior total
int flux[1000][1000];
vector<int> tata;
int m;

int bfs()
{
    queue<int> q;

    for(int i=0; i<=2*n+1; i++)
        tata[i] = -1; //vectorul de tati se modifica la fiecare parcurgere

    q.push(0);
    while(!q.empty())
    {
        int nod = q.front();
        q.pop();
        for(int i = 1; i<= 2*n+1; i++)
        {
            if(flux[nod][i] != 0 && tata[i] == -1) //daca am muchie intre nod si i si i nu e vizitat inca
            {
                tata[i] = nod;
                q.push(i);

                if(i == 2*n+1) //daca am ajuns la final de lant
                {
                    return 1;
                }

            }
        }
    }
    return 0;

}
int main()
{
    in>>n;
    int x, y;
    tata.resize(2*n+2);
    for(int i=1; i<=n; i++)
    {
        in>>x>>y;
        grInt += x;
        grExt += y;
        flux[0][i] = x;
        flux[i+n][2*n+1] = y;
    }

     if(grInt != grExt)
     {
        out<<-1;
        return 0;
     }

     for(int i=1; i<=n; i++)
     {
         for(int j=n+1; j<=2*n; j++)
         {
             if(i != j-n) //intre un nod si dublura sa nu am muchie
                flux[i][j] = 1; //intre oricare nod si alta dublura am muchie
         }
     }

     while(bfs() != 0)
    {
        int nod = 2*n+1;

        while(nod != 0) //revizuiesc gradele pe graful invers
        {
            int t = tata[nod];
            flux[t][nod]--;
            flux[nod][t]++;
            nod = t;
        }
    }

    if((grInt+grExt)/2 < grInt)
    {
        out<<-1;
        return 0;
    }

    out<<(grInt+grExt)/2<<"\n"; //nr total de grade e calculat pt graful dublat

    for(int i=1; i<=n; ++i)
       for(int j=1+n; j<=2*n; j++)
          if(flux[j][i] != 0)
            out<<i<<" "<<j-n<<"\n";



    return 0;
}