Cod sursa(job #2589830)

Utilizator Senth30Denis-Florin Cringanu Senth30 Data 26 martie 2020 22:50:35
Problema Taramul Nicaieri Scor 35
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.48 kb

#include <bits/stdc++.h>
#define INF 2000000000
#define MOD 997

using namespace std;
const int NMAX = 105;

int N, ans;
int father[NMAX];
int capacity[2 * NMAX][2 * NMAX], flow[2 * NMAX][2 * NMAX];
bool seen[2 * NMAX];
vector <int> edges[2 * NMAX];
queue <int> Q;

void read(){
    scanf("%d", &N);
    int a, b;
    for(int i = 1; i <= N; i++){
        scanf("%d%d", &a, &b);
        capacity[0][i] = a;
        edges[0].push_back(i);
        edges[i].push_back(0);
        capacity[N + i][2 * N + 1] = b;
        edges[N + i].push_back(2 * N + 1);
        edges[2 * N + 1].push_back(N + i);
        for(int j = N + 1; j <= 2 * N; j++){
            if(j == N + i) continue;
            capacity[i][j] = 1;
            edges[i].push_back(j);
            edges[j].push_back(i);
        }
    }
}

bool bellman_ford(){
    Q.push(0);
    seen[0] = true;
    while(!Q.empty()){
        int node = Q.front();
        Q.pop();
        for(int i = 0; i < edges[node].size(); i++){
            int x = edges[node][i];
            if(!seen[x] && capacity[node][x] - flow[node][x] > 0){
                Q.push(x);
                father[x] = node;
                seen[x] = true;
            }
        }
    }
    if(!father[2 * N + 1])
        return false;
    int node = 2 * N + 1;
    for(int i = 0; i < edges[node].size(); i++){
        int x = edges[node][i];
        if(capacity[x][node] - flow[x][node] > 0){
            int Min = capacity[x][node] - flow[x][node];
            for(int j = x; j != 0; j = father[j])
                if(Min > capacity[father[j]][j] - flow[father[j]][j])
                    Min = capacity[father[j]][j] - flow[father[j]][j];
            ans += Min;
            flow[x][node] += Min;
            flow[node][x] -= Min;
            for(int j = x; j != 0; j = father[j]){
                flow[father[j]][j] += Min;
                flow[j][father[j]] -= Min;
            }
        }
    }
    return true;
}

int main(){

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

    read();

    bool retry = true;
    while(retry){
        retry = false;
        for(int i = 0; i <= 2 * N + 1; i++){
            seen[i] = 0;
            father[i] = 0;
        }
        retry = bellman_ford();
    }
    printf("%d\n", ans);
    for(int i = N + 1; i <= 2 * N; i++){
        for(int j = 1; j <= N; j++)
            if(flow[i][j])
                printf("%d %d\n", j, i - N);
    }

    return 0;
}