Cod sursa(job #1444233)

Utilizator cernat.catallinFMI Cernat Catalin Stefan cernat.catallin Data 29 mai 2015 13:56:01
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Teme Pregatire ACM Unibuc 2014, Anul I, Semestrul 2 Marime 2.25 kb
#include <cstdio>
#include <queue>
#include <algorithm>
#include <string.h>
using namespace std;
 
#define Nmax 205
int graf[Nmax][Nmax];
int gri[Nmax], gre[Nmax]; // graf interior, grad exterior
int f[Nmax][Nmax], c[Nmax][Nmax], t[Nmax]; // flux, capacitate, tati
int n, flow, s, d;
queue <int> q;
 
void read(){
    scanf("%i", &n);
    for(int i = 1; i <= n; ++i)
        scanf("%i %i", &gre[i], &gri[i]);
    fclose(stdin);
}
 
int bfs(){
    int u;
    q.push(0);
    memset(t, -1, sizeof(t));
 
    while(!q.empty()){
        u = q.front();
        q.pop();
 
        if(u == d){
            while(!q.empty()) q.pop();
            return t[d];
        }
        for(int v = 0; v <= d; ++v)
            if(graf[u][v])
                if( (t[v] == -1) && (c[u][v] != f[u][v]) ){
                    t[v] = u;
                    q.push(v);
                }
    }
    return t[d];
}
 
void max_Flow(){
    int r;
    while(bfs() != -1){
        for(int v = n+1; v <= d-1; ++v)
            if( (t[v] != -1) && (c[v][d] != f[v][d] )){
                r = c[v][d] - f[v][d];
                for(int j = v; j != 0; j = t[j])
                    r = min(r, c[t[j]][j] - f[t[j]][j]);
                if(r > 0){
                    f[v][d] += r;
                    f[d][v] -= r;
                    for(int j = v; j != 0; j = t[j]){
                        f[t[j]][j] += r;
                        f[j][t[j]] -= r;
                    }
                    flow += r;
                }
            }
    }
}
 
void solve(){
    // contruesc graful bipartit si adaug un nod sursa si un nod destinatie
    for(int i = 1; i <= n; ++i)
        for(int j = n+1; j <= 2*n; ++j){
            graf[i][j] = graf[j][i] = 1;
            c[i][j] = 1;
        }
    s = 0; d = 2*n+1;
    for(int i = 1; i <= n; ++i) graf[i][n+i] = 0;
    for(int i = 1; i <= n; ++i){
        graf[s][i] = graf[i][s] = 1;
        c[s][i] = gre[i];
        graf[n+i][d] = graf[d][n+i] = 1;
        c[n+i][d] = gri[i];
    }
    max_Flow();
}
 
void write(){
    printf("%i\n", flow);
    for(int i = 1; i <= n; ++i)
        for(int j = n+1; j <= 2*n; ++j)
            if(f[i][j]) printf("%i %i\n", i, j-n);
}
 
int main(){
    freopen("harta.in", "r", stdin);
    freopen("harta.out", "w", stdout);
 
    read();
    solve();
    write();
}