Cod sursa(job #3189806)

Utilizator iulia_tamasTamas Iulia iulia_tamas Data 6 ianuarie 2024 15:43:02
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.85 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");

#define maxx INT_MAX

class Graf{
private:
    int n;
    int cap[500][500], flux[500][500];
    vector<int> t;
    vector<vector<int>> adc;

public:
    Graf(int n) : n(n){
        adc.resize(n+1);
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                cap[i][j]=0;
                flux[i][j]=0;
            }
        }
    }

    void adauga_muchie(int i, int j){
        adc[i].push_back(j);
        adc[j].push_back(i);
        cap[i][j]=1;

    }

    void adauga_muchie_s(int i, int x){
        adc[0].push_back(i);
        cap[0][i]=x;

    }

    void adauga_muchie_d(int j, int y){
        adc[j].push_back(n-1);
        cap[j][n-1]=y;

    }

    int bfs (int s, int d){
        deque<int> Q;
        vector<int> use(d+1, 0);
        t.assign(d+1, 0);
        Q.push_back(s);
        use[s]=1;
        while(!Q.empty()){
            int nod = Q.front();
            Q.pop_front();
            //cout<<nod<<' ';
            if(nod==d) break;
            for(int i=0; i<adc[nod].size(); i++){
                int vecin=adc[nod][i];
                if(!use[vecin]){
                    if((cap[nod][vecin]-flux[nod][vecin])>0){
                        Q.push_back(vecin);
                        t[vecin]=nod;
                        use[vecin]=1;
                    }
                }
            }
        }
        if(t[d]) return 1;
        return 0;
    }

    int edmond_karp(int s, int d){
        int flow = 0;
        int i, mini;
        while(bfs(s,d)){
            mini= maxx;
            i=d;
            while(i!=0){
                if((cap[t[i]][i] - flux[t[i]][i] )< mini)
                    mini = (cap[t[i]][i] - flux[t[i]][i]);
                i=t[i];
            }
            i=d;
             while(i!=0){
                flux[t[i]][i] += mini;
                flux[i][t[i]] -= mini;
                i=t[i];
            }
            flow += mini;
        }
        return flow;
    }

    void taramul_nicaieri(int s, int d){
        fout<<edmond_karp(s,d)<<endl;
        int m = (d-1)/2;
        for(int i=1; i<=m; i++){
            for(int j=m+1; j<=m+m; j++){
                if(flux[i][j]==1)
                    fout<<i<<' '<<j-m<<endl;
            }
        }
    }

};


int main()
{
    int n;
    int s,d,x,y,c;
    fin>>n;
    s=0;
    d=n+n+1;
    Graf g(d+1);
    for(int i=1; i<=n; i++){
        fin>>x>>y;
        int j=n+i;
        g.adauga_muchie_s(i,x);
        g.adauga_muchie_d(j,y);
    }
    for(int i=1; i<=n; i++){
         for(int j=n+1; j<=n+n; j++){
            if((i%n)!=(j%n)) {
                g.adauga_muchie(i,j);
            }
         }
    }
    g.taramul_nicaieri(s,d);
    return 0;
}