Cod sursa(job #1789650)

Utilizator RaduMirceaAndreiRadu Mircea Andrei RaduMirceaAndrei Data 27 octombrie 2016 12:25:08
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.04 kb
# include <fstream>
# include <vector>
# include <deque>
# include <cstring>
# define DIM 210
# define INF 1000000000
# define pb push_back
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
vector <int> Lista[DIM];
deque <int> d;
int c[DIM][DIM],f[DIM][DIM],sol[2][DIM*DIM],Marcat[DIM],t[DIM];
int n,i,j,k,x,y,dm,mn;
int bfs(){
    int ok=0;
    memset(Marcat,0,sizeof(Marcat));
    Marcat[0]=1;
    d.pb(0);
    while(!d.empty()){
        int nc=d.front();
        if(nc==2*n+1)
            ok=1;
        d.pop_front();
        for(int i=0;i<Lista[nc].size();i++){
            int nv=Lista[nc][i];
            if(Marcat[nv]==0&&f[nc][nv]<c[nc][nv]){
                d.pb(nv);
                Marcat[nv]=1;
                t[nv]=nc;
            }
        }
    }
    return ok;
}
int main () {
    fin>>n;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++){
            if(j==i)
                continue;
            Lista[i].pb(j+n);
            Lista[j+n].pb(i);
            c[i][j+n]=1;
        }
    for(i=1;i<=n;i++){
        fin>>x>>y;
        Lista[0].pb(i);
        Lista[i].pb(0);
        Lista[i+n].pb(2*n+1);
        Lista[2*n+1].pb(i+n);
        c[0][i]=x;
        c[i+n][2*n+1]=y;
    }
    dm=2*n+1;
    t[0]=-1;
    while(bfs()){
        for(j=0;j<Lista[dm].size();j++){
            int nc=Lista[dm][j];
            if(Marcat[nc]&&c[nc][dm]>f[nc][dm]){
                mn=c[nc][dm]-f[nc][dm];
                for(i=nc;t[i]!=-1;i=t[i])
                    mn=min(mn,c[t[i]][i]-f[t[i]][i]);
                f[nc][dm]+=mn;
                f[dm][nc]-=mn;
                for(i=nc;t[i]!=-1;i=t[i]){
                    f[t[i]][i]+=mn;
                    f[i][t[i]]-=mn;
                }
            }
        }
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(f[i][j+n]){
                sol[0][++k]=i;
                sol[1][k]=j;
            }
    fout<<k<<"\n";
    for(i=1;i<=k;i++)
        fout<<sol[0][i]<<" "<<sol[1][i]<<"\n";
    return 0;
}