Cod sursa(job #1830230)

Utilizator grimmerFlorescu Luca grimmer Data 16 decembrie 2016 14:14:08
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.5 kb
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
using namespace std;

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

const int NMAX = 100;
const int  MAXNODE = 2 * NMAX + 2;
vector<int> G[MAXNODE + 5];
int n, parent[MAXNODE + 5], cap[MAXNODE + 5][MAXNODE + 5], flow[MAXNODE + 5][MAXNODE + 5], dest;
bool use[MAXNODE + 5];

bool BFS(){
    memset(use, 0, sizeof use);
    queue<int> q;
    int node, curr_node, i;
    q.push(0);
    use[0] = true;

    while(!q.empty()){
        node = q.front();
        q.pop();

        if(node == dest) continue;

        for(i = 0; i < (int)G[node].size(); ++i){

            curr_node = G[node][i];

            if(!use[curr_node] && flow[node][curr_node] < cap[node][curr_node]){

                q.push(curr_node);
                use[curr_node] = true;
                parent[curr_node] = node;

            }

        }

    }

    return use[dest];
}

int main()
{
    int i, in, out, j, nr_ver = 0, node;
    bool cnt;

    fin>>n;
    dest = 2 * n + 1;

    for(i = 1; i <= n; ++i){
        fin>> out >> in;

        G[0].push_back(i);
        G[i].push_back(0);
        cap[0][i] = out;

        G[n + i].push_back(dest);
        G[dest].push_back(n + i);
        cap[n + i][dest] = in;

        nr_ver += in;
    }

    for(i = 1; i <= n; ++i){
        for(j = 1; j <= n; ++j){
            if(i != j){

                G[i].push_back(n + j);
                G[n + j].push_back(i);
                cap[i][n + j] = 1;

            }
        }
    }

    while(BFS()){

        for(i = 0; i < (int)G[dest].size(); ++i){

            node = G[dest][i];

            if(use[node] && flow[node][dest] < cap[node][dest]){
                parent[dest] = node;
                cnt = true;

                for(j = dest; j != 0; j = parent[j]){

                    if(flow[parent[j]][j] == cap[parent[j]][j]){
                        cnt = false;
                    }

                }

                if(cnt){

                    for(j = dest; j != 0; j = parent[j]){

                        ++flow[parent[j]][j];
                        --flow[j][parent[j]];
                    }

                }

            }

        }

    }

    fout<< nr_ver << "\n";

    for(i = 1; i <= n; ++i){
        for(j = 1; j <= n; ++j){
            if(flow[i][n + j] == 1){

                fout<< i << " " << j << "\n";

            }
        }
    }

    return 0;
}