Cod sursa(job #3188924)

Utilizator PopaBiancaPopa Bianca Daniela PopaBianca Data 4 ianuarie 2024 01:02:39
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 3.25 kb
#include <bits/stdc++.h>

using namespace std;


int const nMax = 2 * 100 + 5;
int const flowMax = 110000 + 5;

int n, m, in, out, k, g;

struct nod{
    int ind;
    int fSent;

};

vector <vector<nod>> graph(nMax);

int findCostPath(int s, int t, vector<int>& f){
    int x = t;
    int ans = flowMax;

    while (x != s)
    {
        int dad = f[x];
        for(auto elm: graph[dad])
            if(elm.ind == x){
                ans = min(ans, elm.fSent);
                if(ans == 0)
                    return 0;
                break;
            }
        x = dad;
    }

    x = t;
    while (x != s)
    {
        int dad = f[x];
        for(auto& elm: graph[x])
            if(elm.ind == dad){
                elm.fSent += ans;
                break;
            }
        for(auto& elm: graph[dad])
            if(elm.ind == x){
                elm.fSent -= ans;
                break;
            }
        x = dad;
    }
    return ans;
}


int findPath(int s, int t){
    vector <int> f(2*n+2, 0);
    vector <bool> viz(2*n+2, false);
    queue <int> q;

    int ans = 0;

    q.push(s);
    viz[s] = true;
    while (!q.empty())
    {
        int x = q.front();
        q.pop();
        //  cout << x << "* ";

        for(auto elm: graph[x]){
            if(!viz[elm.ind] && elm.fSent > 0){
                    f[elm.ind] = x;

                    if(elm.ind == t){
                        ans += findCostPath(s, t, f);
                        // for(int i = s; i < t; i++){
                        // cout << i << ": ";
                        // for(auto elm: graph[i]){
                        //     cout << elm.ind << " " << elm.fSent << ", "; 
                        // }
                        // cout << "\n";
                        //  }
                    }
                    else{
                        q.push(elm.ind);
                        viz[elm.ind] = true;
                    }
            }
        }

    }
    // cout << ans << " ";

    return ans;
}


int fluxMax(int s, int t){

    int maxPush = 0;
    int ans = 0;
    do
    {
        maxPush = findPath(s, t);
        ans += maxPush;
        
    } while (maxPush);
    
    return ans;
}

int main()
{
    freopen("harta.in","r",stdin);
    freopen("harta.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    
    int s = 0;
    int t = 2*n+1;

    for(int i = 1; i <= n; i++){
        cin >> in >> out;
        graph[s].push_back({i, in});
        graph[i].push_back({s, 0});

        graph[i+n].push_back({t, out});
        graph[t].push_back({i+n, 0});
    }

    for(int i = 1; i <=n; i++){
        for(int j = 1; j<= n; j++){
            if(i != j){
                graph[i].push_back({n+j, 1});
                graph[n+j].push_back({i, 0});
            }
        }
    }
    // for(int i = s; i < t; i++){
    //     cout << i << ": ";
    //     for(auto elm: graph[i]){
    //         cout << elm.ind << " " << elm.fSent << ", "; 
    //     }
    //     cout << "\n";
    // }
    // cout << "\n\n";
    
    cout << fluxMax(s, t) << "\n";
    for(int i = 1; i <= n; i++){
        for(auto elm: graph[i]){
            if(elm.ind-n != i && elm.fSent == 0 && elm.ind-n > 0)
                cout << i << " " << elm.ind-n << "\n";
        }
    }

    return 0;
}