Cod sursa(job #1887522)

Utilizator antanaAntonia Boca antana Data 21 februarie 2017 17:24:53
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.18 kb
#include <cstdio>
#include <vector>
#include <cstring>

#define MAXN 202
#define INF 0x3f3f3f3f

using namespace std;

vector <int> G[MAXN];

int source, sink, n, maxflow, flow[MAXN][MAXN], capacity[MAXN][MAXN], dad[MAXN], q[MAXN];
bool seen[MAXN];

inline bool bfs()
{
    int node, left, right, son, i;

    memset(seen, 0, sizeof seen);
    left = right = 0;
    q[right++] = source;
    seen[source] = 1;

    while(left < right) {
        node = q[left++];
        if(node == sink) continue;

        for(i=0; i<G[node].size(); ++i)
        if(!seen[G[node][i]] && flow[node][G[node][i]] < capacity[node][G[node][i]]) {
            son = G[node][i];
            seen[son] = 1;
            dad[son] = node;
            q[right++] = son; } }

    return seen[sink];
}

inline int pump()
{
    int node, a = 0, minflow, i;

    for(i=0; i<G[sink].size(); ++i)
    if(seen[G[sink][i]] && flow[G[sink][i]][sink] < capacity[G[sink][i]][sink]) {
        dad[sink] = G[sink][i];
        minflow = INF;
        for(node=sink; node!=source; node=dad[node])
            minflow = min(minflow, capacity[dad[node]][node] - flow[dad[node]][node]);
        if(minflow)
            for(node=sink; node!=source; node=dad[node])
                flow[dad[node]][node] += minflow, flow[node][dad[node]] -= minflow;
        a += minflow;
    }

    return a;
}

int main()
{
    freopen("harta.in", "r", stdin);
    freopen("harta.out", "w", stdout);

    int i, j, x, y;

    scanf("%d", &n);

    for(i=1; i<=n; ++i) {
        scanf("%d%d", &x, &y);
        G[0].push_back(i);
        G[i].push_back(0);
        capacity[0][i] = x;

        G[2*n+1].push_back(i+n);
        G[i+n].push_back(2*n+1);
        capacity[i+n][2*n+1] = y; }

    for(i=1; i<=n; ++i)
    for(j=n+1; j<=2*n; ++j)
        if(i+n != j) {
            G[i].push_back(j);
            G[j].push_back(i);
            capacity[i][j] = 1; }

    source = 0;
    sink = 2*n+1;

    while(bfs()) maxflow += pump();

    printf("%d\n", maxflow);

    for(i=1; i<=n; ++i)
        for(j=n+1; j<=2*n; ++j)
            if(flow[i][j])
                printf("%d %d\n", i, j-n);
    return 0;
}