Cod sursa(job #2589825)

Utilizator Senth30Denis-Florin Cringanu Senth30 Data 26 martie 2020 22:34:43
Problema Taramul Nicaieri Scor 35
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.1 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];
int flow[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);
        ans += a;
        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);
    flow[0] = 2e9;
    while(!Q.empty()){
        int node = Q.front();
        Q.pop();
        for(int i = 0; i < edges[node].size(); i++){
            int x = edges[node][i];
            if(!capacity[node][x]) continue;
            if(flow[x] < min(flow[node], capacity[node][x])){
                Q.push(x);
                flow[x] = min(flow[node], capacity[node][x]);
                father[x] = node;
            }
        }
    }
    if(!father[2 * N + 1])
        return false;
    int node = 2 * N + 1;
    int x = flow[2 * N + 1];
    while(node != 0){
        capacity[father[node]][node] -= x;
        capacity[node][father[node]] += x;
        node = father[node];
    }
    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++){
            flow[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(capacity[i][j])
                printf("%d %d\n", j, i - N);
    }

    return 0;
}