Cod sursa(job #1164426)

Utilizator beldeabogdanBogdan Beldea beldeabogdan Data 2 aprilie 2014 05:34:50
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.37 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[2*nmax];
//vector <int> r[nmax];
queue <int> q;
int cap[2*nmax][2*nmax];
int flow[2*nmax][2*nmax];
int input;
int output;
int t[2*nmax];
int n,m;
int maxflow;

bool bfs() {
    bool found = false;
    for(int i=0;i<2*nmax;i++)t[i] = -1;
   // 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,&input);
        cap[0][i] = output;
        cap[i+n][n+n+1] = input;
        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 ) {
        g[i].push_back(j+n);
        g[j+n].push_back(i);//rezidualul
        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;
            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;
}