Cod sursa(job #2140176)

Utilizator EuAlexOtaku Hikikomori EuAlex Data 23 februarie 2018 02:25:40
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.54 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>
 
using namespace std;
 
const int inf = 2000000000;
 
struct Muchie {
    int to, rev, flow, cap;
};
 
vector <Muchie> g[204];
int n, src, dr;
 
queue <int> q;
int dist[204];
int bfs() {
    memset(dist, 0, sizeof(dist));
    q.push(src);
    dist[src] = 2;
 
    while(!q.empty()) {
        int from = q.front();
        for(int k = 0; k < g[from].size(); ++ k) {
            Muchie &e = g[from][k];
 
            if(dist[e.to] == 0 && e.flow < e.cap) {
                dist[e.to] = dist[from] + 1;
                q.push(e.to);
            }
        }
        q.pop();
    }
 
    return (dist[dr] > 0);
}
 
int minim(int a, int b) {
    if(a > b)
        return b;
    return a;
}
 
int rem[204];
int dfs(int from, int minflow) {
    if(from == dr) {
        return minflow;
    } else {
        for(int &k = rem[from]; k < g[from].size(); ++ k) {
            Muchie &e = g[from][k];
 
            if(dist[from] == dist[e.to] - 1 && e.flow < e.cap) {
                int deltaflow = dfs(e.to, minim(minflow, e.cap - e.flow));
 
                if(deltaflow > 0) {
                    e.flow += deltaflow;
                    g[e.to][e.rev].flow -= deltaflow;
                    return deltaflow;
                }
            }
        }
        return 0;
    }
}
 
int maxflow() {
    int raspuns = 0, deltaflow;
    while(bfs() == 1) {
        memset(rem, 0, sizeof(rem));
        do {
            deltaflow = dfs(src, inf);
            raspuns += deltaflow;
        }while(deltaflow > 0);
    }
    return raspuns;
}
 
int main() {
    freopen("harta.in", "r", stdin);
    freopen("harta.out", "w", stdout);
 
    scanf("%d", &n);
    n *= 2;
    src = n ++;
    dr = n ++;
 
    for(int i = 0; i < n - 2; i += 2) {
        int out, in;
        scanf("%d%d", &out, &in);
 
        g[i].push_back({dr, g[dr].size(), 0, in});
        g[dr].push_back({i, g[i].size() - 1, 0, 0});
 
        g[src].push_back({i + 1, g[i + 1].size(), 0, out});
        g[i + 1].push_back({src, g[src].size() - 1, 0, 0});
 
        for(int j = 0; j < n - 2; j += 2) {
            if(j != i) {
                g[i + 1].push_back({j, g[j].size(), 0, 1});
                g[j].push_back({i + 1, g[i + 1].size() - 1, 0, 0});
            }
        }
    }
 
    printf("%d\n", maxflow());
 
    for(int i = 1; i < n - 2; i += 2) {
        for(int j = 0; j < g[i].size(); ++ j) {
            if(g[i][j].flow > 0) {
                printf("%d %d\n", i / 2 + 1, g[i][j].to / 2 + 1);
            }
        }
    }
 
    return 0;
}