Cod sursa(job #3193528)

Utilizator Ionut2791Voicila Ionut Marius Ionut2791 Data 14 ianuarie 2024 19:46:03
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 4.19 kb
#include "bits/stdc++.h"
#include <type_traits>
using namespace std;

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimization("unroll-loops")

// ============ Macros starts here ============
int recur_depth = 0;
#ifdef DEBUG
#define dbg(x) {++recur_depth; auto x_=x; --recur_depth; cerr<<string(recur_depth, '\t')<<"\e[91m"<<__func__<<":"<<__LINE__<<"\t"<<#x<<" = "<<x_<<"\e[39m"<<endl;}
#else
#define dbg(x)
#endif // DEBUG
template<typename Ostream, typename Cont>
typename enable_if<is_same<Ostream, ostream>::value, Ostream&>::type operator<<(Ostream& os, const Cont& v) {
    os << "[";
    for (auto& x : v) { os << x << ", "; }
    return os << "]";
}
template<typename Ostream, typename ...Ts>
Ostream& operator<<(Ostream& os, const pair<Ts...>& p) {
    return os << "{" << p.first << ", " << p.second << "}";
}

#define readFast                      \
    ios_base::sync_with_stdio(false); \
    cin.tie(0);                       \
    cout.tie(0);
#ifdef LOCAL
#define read() ifstream fin("date.in.txt")
#else
#define read() readFast
#endif // LOCAL
// ============ Macros ends here ============

#define fin cin
#define ll long long
#define sz(x) (int)(x).size()
#define all(v) v.begin(), v.end()
#define output(x) (((int)(x) && cout << "YES\n") || cout << "NO\n")
#define LSB(x) (x & (-x))
#define test cout << "WORKS\n";

const int N = 2e5 + 15;
const int MOD = 1e9 + 7; // 998244353

int n;
vector<vector<int>> capacity;
vector<vector<int>> adj;
const int INF = 1e9;
int bfs(int s, int t, vector<int>& parent) {
    fill(parent.begin(), parent.end(), -1);
    parent[s] = -2;
    queue<pair<int, int>> q;
    q.push({ s, INF });

    while (!q.empty()) {
        int cur = q.front().first;
        int flow = q.front().second;
        q.pop();

        for (int next : adj[cur]) {
            if (parent[next] == -1 && capacity[cur][next]) {
                parent[next] = cur;
                int new_flow = min(flow, capacity[cur][next]);
                if (next == t)
                    return new_flow;
                q.push({ next, new_flow });
            }
        }
    }

    return 0;
}

int maxflow(int s, int t) {
    int flow = 0;
    vector<int> parent(202);
    int new_flow;

    while (new_flow = bfs(s, t, parent)) {
        flow += new_flow;
        int cur = t;
        while (cur != s) {
            int prev = parent[cur];
            capacity[prev][cur] -= new_flow;
            capacity[cur][prev] += new_flow;
            cur = prev;
        }
    }

    return flow;
}


int main() {
    // read();
    ifstream fin("harta.in");
    ofstream cout("harta.out");
    fin >> n;
    int s = 0, t = n + n + 1;
    capacity.resize(202, vector<int>(202, 0));
    adj.resize(202);

    for (int i = 1; i <= n; ++i) {
        int dgOut, dgIn;
        fin >> dgOut >> dgIn;
        adj[s].push_back(i);
        capacity[s][i] = dgOut;

        adj[n + i].push_back(t);
        capacity[n + i][t] = dgIn;

        for (int j = 1; j <= n; ++j) {
            if (i == j)
                continue;
            adj[i].push_back(n + j);

            capacity[i][n + j] = 1;
            adj[n + j].push_back(i);
            // capacity[n + j][i] = 1;
        }
    }
    cout << maxflow(s, t) << '\n';

    for (int i = 1; i <= n; ++i) {
        for (int x : adj[i]) {
            if (capacity[i][x] == 0) {
                cout << i << " " << x - n << '\n';
            }
        }
    }

    return 0;
} /*stuff you should look for !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
   * test the solution with the given example
   * int overflow, array bounds, matrix bounds
   * special cases (n=1?)
   * do smth instead of nothing and stay organized
   * WRITE STUFF DOWN
   * DON'T GET STUCK ON ONE APPROACH
~Benq~*/

/*
int dsu_find(int nod) {
    if (tata[nod] == nod) {
        return nod;
    }
    return tata[nod] = dsu_find(tata[nod]);
}

bool dsu_union(int a, int b) {
    a = dsu_find(a);
    b = dsu_find(b);
    if (a != b) {
        if (height[a] < height[b])
            swap(a,b);
        tata[a] = b;
        if (height[a] == height[b]) {
            ++height[a];
        }
        return true;
    }
    return false;
}

bool cmp(const vector<int>& a, const vector<int>& b) {
    return a[2] < b[2];
}

*/