Cod sursa(job #1235573)

Utilizator Adrian1997Radulescu Adrian Adrian1997 Data 29 septembrie 2014 23:38:27
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.72 kb
#include <fstream>
#include <bitset>
#include <queue>
#include <list>
#define DIM 310
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int n,z,k;
int T[DIM];
int C[DIM][DIM],F[DIM][DIM];

list<int> L[DIM];
list<int>::iterator it;
queue<int> q;
bitset<DIM> viz;

inline int bfs(){
    int nod;
    viz.reset();
    for(register int i=1;i<=z;i++)
        T[i]=-1;
    q.push(0),viz[0]=1;
    while(!q.empty()){
        nod=q.front(),q.pop();
        for(it=L[nod].begin();it!=L[nod].end();it++){
            if(!viz[*it] && C[nod][*it]>F[nod][*it])
                T[*it]=nod,viz[*it]=1,q.push(*it);
        }
    }
    return viz[z];
}

int main(void){
    register int i,j,x,y,minim;

    f>>n,z=2*n+1;
    for(i=1;i<=n;i++){
        f>>x>>y;
        L[0].push_back(i),L[i].push_back(0);
        L[i+n].push_back(z),L[z].push_back(i+n);
        C[0][i]=x,C[i+n][z]=y;
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i!=j)
                C[i][j+n]=1,L[i].push_back(j+n),L[j+n].push_back(i);

    T[0]=-1;
    while(bfs()){
        for(it=L[z].begin();it!=L[z].end();it++){
            if(viz[*it] && C[*it][z]>F[*it][z]){
                x=*it;
                minim=C[*it][z]-F[*it][z];
                while(T[x]>=0) minim=min(C[T[x]][x]-F[T[x]][x],minim),x=T[x];
                x=*it;
                F[x][z]+=minim,F[z][x]-=minim;
                while(T[x]>=0) F[T[x]][x]+=minim,F[x][T[x]]-=minim,x=T[x];
                k+=minim;
            }
        }
    }

    g<<k<<"\n";
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            if(i!=j && F[i][j+n])
                g<<i<<" "<<j<<"\n";
    f.close();
    g.close();
    return 0;
}