Cod sursa(job #3264602)

Utilizator Alex18maiAlex Enache Alex18mai Data 22 decembrie 2024 17:45:06
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.87 kb
#include <bits/stdc++.h>

using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma GCC optimize("unroll-loops")

void start() {
    freopen("harta.in", "r", stdin); freopen("harta.out", "w", stdout);
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cout << setprecision(12) << fixed;
    srand(time(nullptr));
}


pair<int, vector<vector<int>>> compute_max_flow(int n_nodes, int source, int destination, vector<vector<int>> &cap){
    assert(cap.size() == n_nodes+1);
    for (int i=1; i<=n_nodes; i++){
        assert(cap[i].size() == n_nodes+1);
    }

    vector<vector<int>> gr(n_nodes+1);
    vector<vector<int>> flow(n_nodes+1, vector<int>(n_nodes+1, 0));
    vector<int> dad(n_nodes+1, 0);
    queue<int> q;

    // make gr
    for (int i=1; i<=n_nodes; i++){
        for (int j=1; j<=n_nodes; j++){
            if (cap[i][j]){
                gr[i].push_back(j);
                gr[j].push_back(i);
            }
        }
    }

    // Edmonds Karp
    int ans = 0;
    bool is_flow = true;
	while (is_flow) {
        // bfs
        is_flow = false;
        for (int i = 1; i <= n_nodes; i++) {
            dad[i] = 0;
        }
        dad[source] = source;
        q.push(source);
        while (!q.empty()) {
            int now = q.front();
            q.pop();
            if (now == destination) {
                is_flow = true;
                continue;
            }
            for (auto& x : gr[now]) {
                if (!dad[x] && cap[now][x] - flow[now][x] > 0) {
                    dad[x] = now;
                    q.push(x);
                }
            }
        }

        // apply flow
		for (auto& x : gr[destination]) {
			if (!dad[x]) {
				continue;
			}
			dad[destination] = x;
			int now = destination;
			int MIN = INT_MAX;
			while (now != source) {
				MIN = min(MIN, cap[dad[now]][now] - flow[dad[now]][now]);
				now = dad[now];
			}
			now = destination;
			while (now != source) {
				flow[dad[now]][now] += MIN;
				flow[now][dad[now]] -= MIN;
				now = dad[now];
			}
			ans += MIN;
		}
	}

    return {ans, flow};
}


int n;
vector<int> in, out;

void read() {
    cin>>n;
    in.resize(n+1);
    out.resize(n+1);
    for (int i=1; i<=n; i++){
        cin>>out[i]>>in[i];
    }
}


void solve() {
    read();

    int sum_in = 0, sum_out = 0;
    for (int i=1; i<=n; i++){
        sum_in += in[i];
        sum_out += out[i];
    }

    if (sum_in != sum_out){
        cout<<"NU"<<'\n';
        return;
    }

    // MAKE GRAPH
    int n_nodes = 1 + n + n + 1;
    int source = 1;
    int destination = n_nodes;

    int offset_out = 1;
    int offset_in = 1 + n;

    vector<vector<int>> cap(n_nodes+1, vector<int>(n_nodes+1, 0));

    // source to out
    for (int i=1; i<=n; i++){
        cap[source][i+offset_out] = out[i];
    }

    // out to in
    for (int i=1; i<=n; i++){
        for (int j=1; j<=n; j++){
            if (i == j){
                continue;
            }
            cap[i+offset_out][j+offset_in] = 1;
        }
    }

    // in to destination
    for (int i=1; i<=n; i++){
        cap[i+offset_in][destination] = in[i];
    }

    auto result = compute_max_flow(n_nodes, source, destination, cap);
    int max_flow = result.first;
    vector<vector<int>> flow = result.second;

    if (max_flow != sum_in){
        cout<<"NU"<<'\n';
        return;
    }

    cout<<max_flow<<'\n';

    for (int i=1; i<=n; i++){
        for (int j=1; j<=n; j++){
            if (flow[i+offset_out][j+offset_in]){
                cout<<i<<" "<<j<<'\n';
            }
        }
    }

}



int main(){
    start();

    int t = 1;
    // cin>>t;

    for (int i=1; i<=t; i++){
        solve();
    }

    return 0;
}