Cod sursa(job #2140177)

Utilizator EuAlexOtaku Hikikomori EuAlex Data 23 februarie 2018 02:26:48
Problema Taramul Nicaieri Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.9 kb
#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
 
using namespace std;
 
const int inf = 2000000000;
 
struct Muchie {
    int to, rev, flow, cap;
};
 
vector <Muchie> g[404];
int n, src, dr;
 
queue <int> q;
int dist[404];
int bfs() {
    fill(dist, dist + n, -1);
    q.push(src);
    dist[src] = 0;
 
    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] == -1 && e.flow < e.cap) {
                dist[e.to] = dist[from] + 1;
                q.push(e.to);
            }
        }
        q.pop();
    }
 
    return (dist[dr] > -1);
}
 
int rem[404];
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, min(minflow, e.cap - e.flow));
 
                if(deltaflow > 0) {
                    e.flow += deltaflow;
                    g[e.to][e.rev].flow -= deltaflow;
                    rem[from] = k + 1;
                    return deltaflow;
                }
            }
        }
        return 0;
    }
}
 
int maxflow() {
    int raspuns = 0, deltaflow;
    while(bfs() == 1) {
        fill(rem, rem + n, 0);
        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 *= 4;
    src = n ++;
    dr = n ++;
 
    for(int i = 0; i < n - 2; i += 4) {
        int out, in;
        scanf("%d%d", &out, &in);
 
        g[i].push_back({i + 1, g[i + 1].size(), 0, in});
        g[i + 1].push_back({i, g[i].size() - 1, 0, 0});
 
        g[i + 1].push_back({i + 2, g[i + 2].size(), 0, inf});
        g[i + 2].push_back({i + 1, g[i + 1].size() - 1, 0, 0});
 
        g[i + 2].push_back({i + 3, g[i + 3].size(), 0, out});
        g[i + 3].push_back({i + 2, g[i + 2].size() - 1, 0, 0});
 
        for(int j = 0; j < n; j += 4) {
            if(j != i) {
                g[i + 3].push_back({j, g[j].size(), 0, 1});
                g[j].push_back({i + 3, g[i + 3].size() - 1, 0, 0});
            }
        }
    }
 
    for(int i = 1; i < n; i += 4) {
        g[i].push_back({dr, g[dr].size(), 0, inf});
        g[dr].push_back({i, g[i].size() - 1, 0, 0});
    }
 
    for(int i = 2; i < n; i += 4) {
        g[src].push_back({i, g[i].size(), 0, inf});
        g[i].push_back({src, g[src].size() - 1, 0, 0});
    }
 
    printf("%d\n", maxflow());
 
    for(int i = 3; i < n; i += 4) {
        for(int j = 0; j < g[i].size(); ++ j) {
            if(g[i][j].flow > 0) {
                printf("%d %d\n", i / 4 + 1, g[i][j].to / 4 + 1);
            }
        }
    }
 
    return 0;
}