Cod sursa(job #1513238)

Utilizator alexandra_udristoiuUdristoiu Alexandra Maria alexandra_udristoiu Data 29 octombrie 2015 10:03:06
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include<fstream>
#include<vector>
#include<bitset>
using namespace std;
int n, i, x, y, vecin, d, minim, p, nr, j;
int c[205][205], f[205][205], s[205], t[205];
vector<int> v[205];
bitset<205> viz;
ifstream fin("harta.in");
ofstream fout("harta.out");
int bfs(){
    int p, u, nod, vecin, i;
    int ok = 0;
    viz.reset();
    p = u = 1;
    t[0] = -1;
    s[1] = 0;
    viz[0] = 1;
    while(p <= u){
        nod = s[p];
        for(i = 0; i < v[nod].size(); i++){
            vecin = v[nod][i];
            if(viz[vecin] == 0 && f[nod][vecin] < c[nod][vecin]){
                viz[vecin] = 1;
                u++;
                s[u] = vecin;
                t[vecin] = nod;
                if(vecin == d){
                    ok = 1;
                }
            }
        }
        p++;
    }
    return ok;
}
int main(){
    fin>> n;
    d = 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(d);
        v[d].push_back(n + i);
        c[n + i][d] = y;
    }
    for(i = 1; i <= n; i++){
        for(j = n + 1; j <= 2 * n; j++){
            if(j != n + i){
                v[i].push_back(j);
                v[j].push_back(i);
                c[i][j] = 1;
            }
        }
    }
    while( bfs() ){
        for(i = 0; i < v[d].size(); i++){
            vecin = v[d][i];
            if(viz[vecin] == 1 && f[vecin][d] < c[vecin][d]){
                minim = c[vecin][d] - f[vecin][d];
                p = vecin;
                while(t[p] >= 0){
                    minim = min(minim, c[ t[p] ][p] - f[ t[p] ][p]);
                    p = t[p];
                }

                f[vecin][d] += minim;
                f[d][vecin] -= minim;
                p = vecin;
                while(t[p] >= 0){
                    f[ t[p] ][p] += minim;
                    f[ p][ t[p] ] -= minim;
                    p = t[p];
                }
            }
        }
    }
     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;
}