Cod sursa(job #2180468)

Utilizator circeanubogdanCirceanu Bogdan circeanubogdan Data 20 martie 2018 21:37:53
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.47 kb
#include <fstream>
#include <vector>
#include <queue>
#define DIM 400

using namespace std;

ifstream in ("harta.in");
ofstream out("harta.out");

int n, t[DIM];

struct node{
    int in, out;
}nod[DIM];

vector<int> graf[DIM];

int Cap[DIM][DIM], Flow[DIM][DIM];

bool viz[DIM];

queue<int> q;

bool bfs(){
    for(int i = 0; i <= 2 * n + 1; ++ i)
        viz[i] = false;
    viz[0] = true;
    q.push(0);
    
    while(!q.empty()){
        int nod = q.front();
        q.pop();
        for(int i = 0; i < graf[nod].size(); ++ i){
            int nodc = graf[nod][i];
            if(!viz[nodc] && Cap[nod][nodc] > Flow[nod][nodc]){
                viz[nodc] = true;
                q.push(nodc);
                t[nodc] = nod;
            }
        }
    }
    
    return viz[2 * n + 1];
}

int main(int argc, const char * argv[]) {
    in>>n;
    for(int i = 1; i <= n; ++ i)
        in>>nod[i].in>>nod[i].out;
    
    for(int i = 1; i <= n; ++ i){
        graf[0].push_back(i);
        graf[i].push_back(0);
        Cap[0][i] = nod[i].in;
        for(int j = n + 1; j <= 2 * n; ++ j)
            if(j - i == n)
                continue;
            else{
                graf[i].push_back(j);
                graf[j].push_back(i);
                Cap[i][j] = 1;
            }
    }
    
    for(int i = n + 1; i <= 2 * n; ++ i){
        graf[i].push_back(2 * n + 1);
        graf[2 * n + 1].push_back(i);
        Cap[i][2 * n + 1] = nod[i - n].out;
    }
    
    while(bfs()){
        int N = 2 * n + 1;
        for(int i = 0; i < graf[N].size(); ++ i){
            int nod = graf[N][i];
            if(!viz[nod] || Cap[nod][N] <= Flow[nod][N]) continue;
            int minim = Cap[nod][N] - Flow[nod][N];
            while(nod != 0){
                minim = min(minim, Cap[t[nod]][nod] - Flow[t[nod]][nod]);
                nod = t[nod];
            }
            nod = graf[N][i];
            Flow[nod][N] += minim;
            Flow[N][nod] -= minim;
            while(nod != 0){
                Flow[t[nod]][nod] += minim;
                Flow[nod][t[nod]] -= minim;
                nod = t[nod];
            }
        }
    }
    
    int nr = 0;
    
    for(int i = 1; i <= n; ++ i){
        for(int j = n + 1; j <= 2 * n; ++ j){
            if(Flow[i][j] > 0)
                ++ nr;
        }
    }
    
    out<<nr<<'\n';
    
    for(int i = 1; i <= n; ++ i){
        for(int j = n + 1; j <= 2 * n; ++ j){
            if(Flow[i][j] > 0)
                out<<i<<" "<<j - n<<'\n';
        }
    }
    
    return 0;
}