Cod sursa(job #1205656)

Utilizator smaraldaSmaranda Dinu smaralda Data 7 iulie 2014 16:14:33
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.56 kb
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<string.h>
using namespace std;

const int NMAX = 200, SRC = 0, INF = 2e9;

int n, DEST, cap[NMAX + 5][NMAX + 5], flow[NMAX + 5][NMAX + 5], dad[NMAX + 5];
bool vis[NMAX + 5];
queue <int> q;

bool bfs() {
    int i, node;

    memset(vis, 0, sizeof(vis));
    memset(dad, 0, sizeof(dad));
    while(!q.empty())
        q.pop();

    vis[SRC] = 0;
    for(i = 1; i <= n; ++ i)
        if(cap[SRC][i] > flow[SRC][i]) {
            q.push(i);
            vis[i] = 1;
            dad[i] = SRC;
        }

    while(!q.empty()) {
        node = q.front();
        q.pop();

        if(node <= n) {
            for(i = n + 1; i <= DEST; ++ i)
                if(i - n != node && cap[node][i] > flow[node][i] && !vis[i]) {
                    dad[i] = node;
                    vis[i] = 1;
                    q.push(i);
                }
        }
        else {
            if(cap[node][DEST] > flow[node][DEST] && !vis[DEST]) {
                dad[DEST] = node;
                vis[DEST] = 1;
            }

            for(i = 1; i <= n; ++ i)
                if(i != node - n && cap[node][i] > flow[node][i] && !vis[i]) {
                    dad[i] = node;
                    vis[i] = node;
                    q.push(i);
                }
        }
    }

    if(vis[DEST])
        return 1;
    return 0;
}

int main() {
    freopen("harta.in", "r", stdin);
    freopen("harta.out", "w", stdout);
    int nEdge, j, i, in, node, out, minFlow;

    scanf("%d", &n);
    DEST = 2 * n + 1;

    nEdge = 0;
    for(i = 1; i <= n; ++ i) {
        scanf("%d%d", &in, &out);
        nEdge += in + out;

        cap[SRC][i] = in;
        for(j = 1; j <= n; ++ j)
            if(i != j)
                cap[i][j + n] = 1;
        cap[i + n][DEST] = out;
    }

    while(bfs()) {
        for(i = n + 1; i < DEST; ++ i)
            if(vis[i]) {
                dad[DEST] = i;

                minFlow = INF;
                node = DEST;
                while(node != SRC) {
                    minFlow = min(minFlow, cap[dad[node]][node] - flow[dad[node]][node]);
                    node = dad[node];
                }
 
                node = DEST;
                while(node != SRC) {
                    flow[dad[node]][node] += minFlow;
                    flow[node][dad[node]] -= minFlow;

                    node = dad[node];
                }
            }
    }
    printf("%d\n", nEdge / 2);
    for(i = 1; i <= n; ++ i)
        for(j = 1; j <= n; ++ j)
            if(i != j && flow[i][j + n] == 1)
                printf("%d %d\n", i, j);
    return 0;
}