Cod sursa(job #1513960)

Utilizator robx12lnLinca Robert robx12ln Data 30 octombrie 2015 12:42:54
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.45 kb
#include<fstream>
#include<vector>
#include<cstring>
#include<deque>
#define DIM 210
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int C[DIM][DIM],F[DIM][DIM],s[DIM],t[DIM],n;
vector<int> L[DIM];
deque<int> d;
int bfs(){
   int ok=0;
   memset(s,0,sizeof(s));
   d.push_back(0);
   s[0]=1;
   t[0]=-1;
   while( !d.empty() ){
        int nod = d.front();
        for(int i=0; i < L[nod].size() ; i++ ){
            int vecin = L[nod][i];
            if( s[vecin] == 0 && C[nod][vecin] > F[nod][vecin] ){
                s[vecin] = 1;
                d.push_back(vecin);
                t[vecin] = nod;
                if( vecin == 2*n+1 ){
                    ok = 1;
                }
            }
        }
        d.pop_front();
   }
   return ok;
}
int i,x,y,j,minim,p;
int main(){
    fin>>n;
    for(i=1;i<=n;i++){
        fin>>x>>y;
        //
        C[0][i]=x;
        L[0].push_back(i);
        L[i].push_back(0);
        //
        C[n+i][2*n+1]=y;
        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!=j-n){
                C[i][j]=1;
                L[i].push_back(j);
                L[j].push_back(i);
            }
        }
    }
    while( bfs()==1 ){
        for( i = 0 ; i < L[2*n+1].size() ; i++ ){
            int vecin = L[2*n+1][i];
            if( C[vecin][2*n+1] > F[vecin][2*n+1] && s[vecin] == 1 ){
                minim = C[vecin][2*n+1] - F[vecin][2*n+1] ;
                p=vecin;
                while(t[p] != -1){
                    if( C[ t[p] ][p] - F[ t[p] ][p] < minim ){
                        minim = C[ t[p] ][p] - F[ t[p] ][p] ;
                    }
                    p=t[p];
                }

                F[ vecin ][2*n+1]+=minim;
                F[ 2*n+1 ][vecin]-=minim;

                p=vecin;
                while(t[p] != -1){
                    F[ t[p] ][p]+=minim;
                    F[p][ t[p] ]-=minim;
                    p=t[p];
                }

            }
        }

    }
    int nr=0;
    for(i=1;i<=n;i++){
        for(j=n+1;j<=2*n;j++){
            if( F[i][j] == 1 ){
                nr++;
            }
        }
    }
    fout<<nr<<"\n";
    for(i=1;i<=n;i++){
        for(j=n+1;j<=2*n;j++){
            if( F[i][j] == 1 ){
                fout<<i<<" "<<j-n<<"\n";
            }
        }
    }
    return 0;
}