Cod sursa(job #2469794)

Utilizator TheSeekerRobert Cristian Dobra TheSeeker Data 7 octombrie 2019 23:55:21
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.9 kb
#include <fstream>
#include <vector>
#include <deque>
#define DIM 210
using namespace std;

ifstream fin ("harta.in");
ofstream fout("harta.out");

int n,i,j,f,x,y,nod,vecin,minim,C[DIM][DIM],F[DIM][DIM],T[DIM],ok[DIM];
vector< int > L[DIM];
deque< int > q;

int bfs(){
    ok[0]=1;
    for (i=1;i<=2*n+1;i++)
        ok[i]=0;
    q.push_back(0);
    while (!q.empty()){
        nod=q.front();
        q.pop_front();
        for (i=0;i<L[nod].size();i++){
            vecin=L[nod][i];
            if (!ok[vecin] && C[nod][vecin]>F[nod][vecin]){
                ok[vecin]=1;
                T[vecin]=nod;
                q.push_back(vecin);
            }
        }
    }
    return ok[2*n+1];
}

int main(){
    fin>>n;
    for (i=1;i<=n;i++){
        fin>>x>>y;
        C[0][i]=x;
        C[n+i][2*n+1]=y;
        L[0].push_back(i);
        L[i].push_back(0);
        L[n+i].push_back(2*n+1);
        L[2*n+1].push_back(n+i);
    }
    for (i=1;i<=n;i++)
        for (j=n+1;j<=2*n;j++)
            if (i+n!=j){
                L[i].push_back(j);
                L[j].push_back(i);
                C[i][j]=1;
            }
    while (bfs())
        for (i=0;i<L[2*n+1].size();i++){
            nod=L[2*n+1][i];
            if (ok[nod] && C[nod][2*n+1]>F[nod][2*n+1]){
                minim=C[nod][2*n+1]-F[nod][2*n+1];
                for (j=nod;j!=0;j=T[j])
                    minim=min(minim,C[T[j]][j]-F[T[j]][j]);
                f+=minim;
                F[nod][2*n+1]+=minim;
                F[2*n+1][nod]-=minim;
                for (j=nod;j!=0;j=T[j]){
                    F[T[j]][j]+=minim;
                    F[j][T[j]]-=minim;
                }
            }
        }
    fout<<f<<'\n';
    for (i=1;i<=n;i++)
        for (j=1;j<=n;j++)
            if (F[i][n+j]==1)
                fout<<i<<" "<<j<<'\n';
    fin.close();
    fout.close();
    return 0;
}