Cod sursa(job #1163370)

Utilizator beldeabogdanBogdan Beldea beldeabogdan Data 1 aprilie 2014 12:30:35
Problema Taramul Nicaieri Scor 5
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#include <cstdio>
#include <vector>
#define nmax 105
#define boolMax(a,b) (a)?(true):(b)
using namespace std;

vector <int> g[nmax];
int n,sum;
int input[nmax],output[nmax];

bool existent(int a,int b) {
    for (vector <int> :: iterator it = g[a].begin();it != g[a].end();it++) {
        if (*it == b) return true;
    }
    return false;
}

bool link(int x) {
    for (int i=1;i<=n;i++) {
        if (i == x) continue;
        if (input[i] > 0 && !existent(x,i)) {
            input[i]--;
            output[x]--;
            g[x].push_back(i);
            return true;
        }
    }
    return false;
}

bool insert(int x) {
    for (int i=1;i <= n;i++) {
        if (i == x) continue;
        for (vector <int> :: iterator it = g[i].begin();it != g[i].end();it++) {
            int ct = *it;
            if (ct == x) continue;
            if (existent(i,x) || existent(x,ct)) continue;
            g[i].erase(it);
            g[i].push_back(x);
            g[x].push_back(ct);
            input[x]--,output[x]--;
            return true;
        }
    }
    return false;
}

int main() {
    freopen("harta.in","r",stdin);
    freopen("harta.out","w",stdout);
    scanf("%d",&n);
    for (int i=1;i<=n;i++) {
        scanf("%d %d",&output[i],&input[i]);
        sum += output[i];
    }
    for (int i=1;i<=n;i++) if (output[i] > 0) link(i);
    for (bool changed = true;changed;) {
        changed = false;
        for (int i=1;i<=n;i++) {
            if (output[i] > input[i]) changed = boolMax(link(i),changed);
            else if (output[i] > 0 && input[i] > 0) changed = boolMax(insert(i),changed);
        }
    }
    printf("%d\n",sum);
    for (int i=1;i<=n;i++) {
        for (vector <int> :: iterator it = g[i].begin();it != g[i].end();it++) {
            printf("%d %d\n",i,*it);
        }
    }
    return 0;
}