Cod sursa(job #2662211)

Utilizator divianegoescuDivia Negoescu divianegoescu Data 23 octombrie 2020 18:01:15
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.81 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;
}