Cod sursa(job #2951232)

Utilizator Katherine456719Swan Katherine Katherine456719 Data 5 decembrie 2022 19:01:40
Problema Taramul Nicaieri Scor 35
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.61 kb
#include <iostream>
#include<fstream>

using namespace std;

int n;
int indeg[101],outdeg[101],up[205],queue[101];
int graf[202][202],insum,outsum,flow;


int augument(){
    int head, tail;
    for (int i = 0; i < 2 * n + 2; i++) {
        queue[i] = 0;
        up[i] = -1;
    }

    queue[0] = 0;
    up[0] = 0;
    for (head = tail = 0; head <= tail; head++){
        int i = queue[head];
        for (int j = 0; j < 2 * n + 2; j++)
            if (graf[i][j] && up[j] == -1){
                up[j] = i;
                queue[++tail] = j;
                if (j == 2 * n + 1) {
                    flow++;
                    return 1;
                }
            }
    }
    return 0;
}


void solve(){
    for(int i=1;i<=n;++i)
        for(int j=0;j<=n;++j)
            if(i!=j)
                graf[i][j+n] = 1;
    while (augument())
        for (int i = 2 * n + 1; i; i = up[i]) {
            graf[up[i]][i]--;
            graf[i][up[i]]++;
        }
}

int main(){
    ifstream fin("harta.in");
    ofstream fout("harta.out");
    fin >> n;
    for(int i = 1;i <= n; ++i){
        fin >> indeg[i] >> outdeg[i];
        graf[0][i] = indeg[i];
        graf[i + n][2 * n + 1] = outdeg[i];
        insum += indeg[i];
        outsum += outdeg[i];
    }
    if(insum != outsum)
        fout << "-1\n";
    solve();
    if (flow < insum) {
        fout<<"-1\n";
        return 0;
    }
    fout<<flow<<"\n";
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (graf[j + n][i])
                fout << i << " " <<j <<"\n";
   return 0;
}