Cod sursa(job #1052279)

Utilizator paunmatei7FMI Paun Matei paunmatei7 Data 11 decembrie 2013 00:01:59
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>

#define x first
#define y second
#define NMAX 307
#define INF 100000000

using namespace std;

int Cap[NMAX][NMAX], Flux[NMAX][NMAX], Viz[NMAX], dad[NMAX];
int n, Maxflow, m, sursa, dest;
vector <int> v[NMAX];

inline int dfs(int Nod, int dest){
    if(Nod == dest)
        return 1;
    Viz[Nod] = 1;
    for(int i = 0; i < v[Nod].size(); ++ i){
        int it = v[Nod][i];
        if(Viz[it] == -1 && Flux[Nod][it] != Cap[Nod][it]){
            dad[it] = Nod;
            int ok = dfs(it, dest);
            if(ok == 1)
                return 1;
        }
    }
    return 0;
}

inline int father(int Nod, int Min){
    if(Nod == sursa)
        return Min;
    int Dad = dad[Nod];
    Min = min(Min, Cap[Dad][Nod] - Flux[Dad][Nod]);
    return father(dad[Nod], Min);
}

void father2(int Nod, int Min){
    if(Nod == sursa)
        return;
    int Dad = dad[Nod];
    Flux[Nod][Dad] -= Min;
    Flux[Dad][Nod] += Min;
    father2(dad[Nod], Min);
}

int main(){
    freopen("harta.in", "r", stdin);
    freopen("harta.out", "w", stdout);
    scanf("%d", &n);
    sursa = n * 3;
    dest = n * 2 + 1;
    for(int i = 1; i <= n; ++i){
        int a = 0, b = 0;
        scanf("%d %d", &a, &b);
        Cap[sursa][i] = a;
        Cap[i + n][dest] = b;
        v[sursa].push_back(i);
        v[i].push_back(sursa);
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            if(i != j){
                Cap[i][j + n] = 1;
                v[i].push_back(n + j);
                v[n + j].push_back(i);
            }
    for(int j = 1; j <= n; ++ j){
        v[dest].push_back(j + n);
        v[j + n].push_back(dest);
    }
    memset(dad, -1, sizeof(dad));
    memset(Viz, -1, sizeof(Viz));
    while(dfs(sursa, dest)){
        int Min = INF;
        memset(Viz, -1, sizeof(Viz));
        Min = father(dest, Min);
        Maxflow += Min;
        father2(dest, Min);
        memset(dad, -1, sizeof(dad));
    }
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            if(Flux[i][j + n] > 0)
                ++ m;
    printf("%d\n", m);
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            if(Flux[i][j + n] > 0)
                printf("%d %d\n", i, j);
    return 0;
}