Cod sursa(job #2666900)

Utilizator betybety bety bety Data 2 noiembrie 2020 16:24:58
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.94 kb

#include <fstream>

#include <vector>

#include <bitset>

#define K 204

using namespace std;

ifstream fin("harta.in");

ofstream fout("harta.out");

int n,i,j,x,y,f[K][K],c[K][K],q[K],t[K],tata,vecin,N,scad,flux;

bitset <K> viz;

vector <int> v[K];

int bfs(){

    int p,u;

    viz.reset();

    q[1]=0; viz[0]=1;

    for(p=u=1;p<=u;p++){

        int nod=q[p];

        for(int i=0;i<v[nod].size();i++){

            int vecin=v[nod][i];

            if(!viz[vecin] && c[nod][vecin]>f[nod][vecin]){

                q[++u]=vecin;

                viz[vecin]=1;

                t[vecin]=nod;

                if(vecin==N)

                    return 1;

            }

        }

    }

    return 0;

}

int main(){

    fin>>n; N=2*n+1;

    for(i=1;i<=n;i++){

        fin>>x>>y;

        v[0].push_back(i);

        v[i].push_back(0);

        c[0][i]=x;

        v[n+i].push_back(N);

        v[N].push_back(n+i);

        c[n+i][N]=y;

    }

    for(i=1;i<=n;i++)

        for(j=n+1;j<N;j++)

            if(j-i!=n){

                v[i].push_back(j);

                v[j].push_back(i);

                c[i][j]=1;

            }

    while(bfs()){

        for(i=0;i<v[N].size();i++){

            vecin=v[N][i];

            if(viz[vecin] && c[vecin][N]>f[vecin][N]){

                scad=c[vecin][N]-f[vecin][N];

                for(x=vecin;x>0;x=t[x])

                    scad=min(scad,c[t[x]][x]-f[t[x]][x]);

                f[vecin][N]+=scad;

                f[N][vecin]-=scad;

                flux+=scad;

                for(x=vecin;x>0;x=t[x])

                    f[t[x]][x]+=scad,

                    f[x][t[x]]-=scad;

            }

        }

    }

    fout<<flux<<"\n";

    for(i=1;i<=n;i++)

        for(j=n+1;j<N;j++)

            if(f[i][j]==1)

                fout<<i<<" "<<j-n<<"\n";

    return 0;

}