Cod sursa(job #2665498)

Utilizator Vlad.Vlad Cristian Vlad. Data 30 octombrie 2020 22:16:18
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.63 kb
#include <fstream>
#include <vector>
#include <iostream>
#include <cstring>
#include <queue>
#define NMAX 1005
#define INF 999999
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
vector<pair<int, int>> v;
vector<vector<int>> gr;
int cap[NMAX][NMAX], val[NMAX][NMAX];
int N, M;
void read() {
    int x, y;
    fin >> N;
    for (int i = 0; i < N; ++i) {
        fin >> x >> y;
        v.emplace_back(x, y);
    }
    gr.resize(2 * N + 4);
}
void createGraf() {
    //sursa -> prima parte
    for (int i = 0; i < N; ++i) {
        gr[1].push_back(i + 2);
        gr[i + 2].push_back(1);
        cap[1][i + 2] = v[i].first;
    }
    //prima parte -> a doua parte
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (i != j) {
                gr[i + 2].push_back(j + N + 2);
                gr[j + N + 2].push_back(i + 2);
                cap[i + 2][j + N + 2] = 1;
            }
        }
    }
    //a doua parte -> destinatia
    for (int i = 0; i < N; ++i) {
        gr[i + N + 2].push_back(2 * N + 2);
        gr[2 * N + 2].push_back(i + N + 2);
        cap[i + N + 2][2 * N + 2] = v[i].second;
    }
}
queue<int> q;
int t[NMAX];
bool d[NMAX];
void BFS() {
    int node = 1;
    q.push(node);
    d[node] = true;
    while (!q.empty()) {
        node = q.front();
        q.pop();
        for (int i : gr[node]) {
            if (d[i] == false && val[node][i] < cap[node][i]) {
                d[i] = true;
                t[i] = node;
                q.push(i);
            }
        }
    }
}
int main()
{
    read();
    createGraf();
    bool ok = true;
    int lmin;
    while (ok) {
        memset(t, 0, sizeof t);
        memset(d, false, sizeof d);
        BFS();
        t[0] = -1;
        ok = false;
        lmin = INF;
        for (int i = 2 * N + 2; i > 0; i = t[i]) {
            if (i == 1) {
                ok = true;
            }
            else {
                lmin = min(lmin, cap[t[i]][i] - val[t[i]][i]);
            }
        }
        if (ok) {
            for (int i = 2 * N + 2; i > 1; i = t[i]) {
                val[t[i]][i] += lmin;
                val[i][t[i]] -= lmin;
            }
        }
    }
    vector<pair<int, int>> v;
    int con = 0;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            if (val[i + 2][j + N + 2] != 0) {
                v.emplace_back(i + 1, j + 1);
            }
        }
    }
    fout << v.size() << "\n";
    for (int i = 0; i < v.size(); ++i) {
        fout << v[i].first << " " << v[i].second << "\n";
    }
    return 0;
}