Cod sursa(job #2603464)

Utilizator anamariatoaderAna Toader anamariatoader Data 19 aprilie 2020 23:43:02
Problema Taramul Nicaieri Scor 35
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <fstream>
#include <vector>
#include <cstring>
#include <queue>

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

int n, in, out, i, j, c[205][205], f[205][205], tata[205];
bool viz[205];
struct muchie{
    int x, y;
};
vector <int> g[105];
vector <muchie> sol;
queue <int> q;

void que(){
    memset(viz, 0, sizeof(viz));
    viz[0] = 1, q.push(0);
    while(!q.empty()){
        int nod = q.front();
        q.pop();
        for(int i = 0; i < g[nod].size(); i++){
            int nou = g[nod][i];
            if(!viz[nou] && f[nod][nou] < c[nod][nou])
                viz[nou] = 1, tata[nou] = nod, q.push(nou);
        }
    }
}

int mi(int nod){
    int Min = c[nod][2*n+1] - f[nod][2*n+1];
    while(nod){
        int nou = tata[nod];
        Min = min(Min, c[nou][nod] - f[nou][nod]);
        nod = nou;
    }
    return Min;
}

void back(){
    for(int i = 0; i < g[2*n+1].size(); i++){
        int nod = g[2*n+1][i];
        if(viz[nod]){
            int Min = mi(nod);
            if(!Min)
                continue;
            f[nod][2*n+1] += Min;
            f[2*n+1][nod] -= Min;
            while(nod){
                int nou = tata[nod];
                f[nou][nod] += Min;
                f[nod][nou] -= Min;
                nod = nou;
            }
        }
    }
}

int main()
{
    fin >> n;
    for(i = 1; i <= n; i++){
        fin >> in >> out;
        if(in){
            g[0].push_back(i), g[i].push_back(0);
            c[0][i] = in;

            for(j = 1; j <= n; j++)
              if(i != j)
                g[i].push_back(n+j), g[n+j].push_back(i),
                c[i][n+j] = 1;

        }

        if(out)
            g[i+n].push_back(2*n+1), g[2*n+1].push_back(i+n),
            c[i+n][2*n+1] = out;

    }

    while(!viz[2*n+1]){
        que();
        if(viz[2*n+1])
            back();
        viz[2*n+1] = !viz[2*n+1];
    }

    for(i = 1; i <= n; i++)
        for(j = n+1; j <= 2*n; j++)
            if(f[i][j])
                sol.push_back({i,j-n});

    fout << sol.size() << '\n';
    for(i = 0; i < sol.size(); i++)
        fout << sol[i].x << ' ' << sol[i].y << '\n';
    return 0;
}