Cod sursa(job #2589746)

Utilizator Senth30Denis-Florin Cringanu Senth30 Data 26 martie 2020 20:05:25
Problema Taramul Nicaieri Scor 35
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.35 kb
#include <bits/stdc++.h>
#define INF 2000000000
#define MOD 997

using namespace std;
const int NMAX = 105;

int N, ans;
int capInput[NMAX], capOutput[NMAX];
int Left[NMAX][NMAX];
bool seen[NMAX];
vector <int> edges[NMAX];
pair <int, int> Right[NMAX][NMAX];

void read(){
    scanf("%d", &N);
    for(int i = 1; i <= N; i++)
        scanf("%d%d", &capInput[i], &capOutput[i]);
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= N; j++){
            if(i == j) continue;
            edges[i].push_back(j);
        }
}

bool cuplaj(int node, int pos){
    if(seen[node]) return false;
    seen[node] = true;
    for(int i = 1; i <= N; i++){
        if(i == node) continue;
        bool ok = true;
        for(int j = 1; j <= Left[node][0]; j++)
            if(Left[node][j] == i){
                ok = false;
                break;
            }
        if(ok){
            if(Right[i][0].first < capOutput[i]){
                Right[i][Right[i][0].first + 1] = {node, pos};
                Right[i][0].first++;
                Left[node][pos] = i;
                Left[node][0] = max(pos, Left[node][0]);
                return true;
            }
        }
    }
    for(int i = 1; i <= N; i++){
        bool ok = true;
        for(int j = 1; j <= Left[node][0]; j++)
            if(Left[node][j] == i){
                ok = false;
                break;
            }
        if(ok)
            for(int j = 1; j <= Right[i][0].first; i++)
                if(cuplaj(Right[i][j].first, Right[i][j].second)){
                    Right[i][j] = {node, pos};
                    Left[node][pos] = i;
                    Left[node][0] = max(pos, Left[node][0]);
                    return true;
                }
    }
}

int main(){

    freopen("harta.in", "r", stdin);
    freopen("harta.out", "w", stdout);

    read();

    bool retry = true;
    while(retry){
        retry = false;
        for(int i = 1; i <= N; i++)
            seen[i] = false;
        for(int i = 1; i <= N; i++)
            if(Left[i][0] < capInput[i])
                retry |= cuplaj(i, Left[i][0] + 1);
    }
    for(int i = 1; i <= N; i++)
        ans += Left[i][0];
    printf("%d\n", ans);
    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= Left[i][0]; j++)
            printf("%d %d\n", i, Left[i][j]);

    return 0;
}