Cod sursa(job #1164421)

Utilizator beldeabogdanBogdan Beldea beldeabogdan Data 2 aprilie 2014 05:06:38
Problema Taramul Nicaieri Scor 35
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#define minim(a,b) (a<b)?(a):(b)
#define nmax 105
using namespace std;

vector <int> g[nmax];
vector <int> r[nmax];
queue <int> q;
int cap[2*nmax][2*nmax];
int flow[2*nmax][2*nmax];
int input[nmax];
int output[nmax];
int t[nmax];
int n,m;
int maxflow;

bool bfs() {
    bool found = false;
    memset(t,-1,nmax*4);
    t[0] = -2;
    q.push(0);
    while (!q.empty()) {
        int ct = q.front(); q.pop();
        for (vector <int> :: iterator it = g[ct].begin();it != g[ct].end();it++) {
            if (cap[ct][*it] - flow[ct][*it] > 0 && t[*it] == -1) {
                if (*it != n+n+1) {
                    q.push(*it);
                    t[*it] = ct;
                } else {
                    found = true;
                }
            }
        }
    }
    return found;
}

int getMin(int x) {
    if (t[x] >= 0) {
        int newMin = getMin(t[x]);
        return minim(newMin,cap[t[x]][x] - flow[t[x]][x]);
    }
    return 0x3fffffff;
}

void update(int x,int value) {
    if (t[x] >= 0) {
        r[t[x]].push_back(x-n);
        flow[t[x]][x] += value;
        flow[x][t[x]] -= value;
        update(t[x],value);
    }
}

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]);
        cap[0][i] = output[i];
        cap[i+n][n+n+1] = input[i];
        g[0].push_back(i);
        g[i].push_back(0);
        g[i+n].push_back(n+n+1);
        g[n+n+1].push_back(i+n);
    }
    for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) if (i != j && output[i] && input[j]) {
        g[i].push_back(j+n); g[j+n].push_back(i);
        cap[i][j+n] = 1;
    }
    while (bfs()) {
        for (vector <int> :: iterator it = g[n+n+1].begin(); it != g[n+n+1].end();it++) {
            t[n+n+1] = *it;
            int ct = n+n+1;
            if (cap[*it][n+n+1] > flow[*it][n+n+1] && t[*it] >= 0) {
                int min = getMin(n+n+1);
                if(min <= 0) continue;
                maxflow += min;
                update(n+n+1,min);
            }
        }
    }
    printf("%d\n",maxflow);
    for (int i=1;i<=n;i++) {
        for(int j =1; j<=n;j++)
        if(flow[i][n+j] == 1 )
        printf("%d %d\n",i,j);
    }
    return 0;
}