Cod sursa(job #3185055)

Utilizator iulia_tamasTamas Iulia iulia_tamas Data 17 decembrie 2023 18:33:54
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");

#define maxx INT_MAX
#define N 1001
int cap[N][N], flux[N][N];
vector<int> t;
vector<int> adc[N];
int n;

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;
    //cout<<"hdx";
    while(bfs(s,d)){
        //cout<<"hdx";
        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){
            //cout<<i<<' ';
            flux[t[i]][i] += mini;
            flux[i][t[i]] -= mini;
            i=t[i];
        }
        //cout<<endl;
        flow += mini;
    }
    return flow;
}


int main()
{
    int s,d,x,y,c;
    fin>>n;
    s=0;
    d=n+n+1;
    for(int i=1; i<=n; i++){
        fin>>x>>y;
        int j=n+i;
        //adc[i].push_back(s);
        adc[s].push_back(i);
        //adc[d].push_back(j);
        adc[j].push_back(d);
        cap[s][i]=x;
        cap[j][d]=y;
    }
    for(int i=1; i<=n; i++){
         for(int j=n+1; j<=n+n; j++){
            if((i%n)!=(j%n)) {
                adc[i].push_back(j);
                adc[j].push_back(i);
                cap[i][j]=1;
            }
         }
    }

    /*for(int i=0; i<=n+n+1; i++){
            cout<<i<<": ";
        for(int j=0; j<adc[i].size(); j++){
            cout<<adc[i][j]<<", "<<cap[i][adc[i][j]]<<"    ";
        }
        cout<<endl;
    }*/

    fout<<edmond_karp(s,d)<<endl;
    for(int i=1; i<=n; i++){
        for(int j=n+1; j<=n+n; j++){
            if(flux[i][j]==1)
                fout<<i<<' '<<j-n<<endl;
        }
    }
    return 0;
}