Cod sursa(job #2951992)

Utilizator andreic06Andrei Calota andreic06 Data 7 decembrie 2022 23:10:08
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.79 kb
#include <bits/stdc++.h>

using namespace std;
const int VMAX = 1e2;
const int INF = 2e9;
const int NONE = -1;

struct MaxFlow {
    int cap[1 + 2 * VMAX][1 + 2 * VMAX], flow[1 + 2 * VMAX][1 + 2 * VMAX];
    bool visited[1 + 2 * VMAX]; int prev[1 + 2 * VMAX];
    int V; int source, sink;


    void add_edge (int a, int b, int c) {
        cap[a][b] = c;
        flow[a][b] = 0;
    }
    bool bfs () {
       for (int node = 0; node <= 2 * V + 1; node ++) {
          prev[node] = NONE;
          visited[node] = false;
       }

       queue<int> q; q.push (source); visited[source] = true;
       while (!q.empty ()) {
          int node = q.front (); q.pop ();
          for (int nxt = 1; nxt <= 2 * V + 1; nxt ++) {
             if (!visited[nxt] && flow[node][nxt] < cap[node][nxt]) {
               q.push (nxt); visited[nxt] = true; prev[nxt] = node;
               if (nxt == sink)
                 return true;
             }
          }
       }
       return false;
    }
    int solve () {
       int maxFlow = 0;
       while (bfs ()) {
          for (int node = V + 1; node <= 2 * V; node ++) {
             if (visited[node] && flow[node][sink] < cap[node][sink]) {
               prev[sink] = node;
               int curr = sink, addFlow = INF;
               while (curr != source) {
                  addFlow = min(addFlow, cap[prev[curr]][curr] - flow[prev[curr]][curr]);
                  curr = prev[curr];
               }
               curr = sink;
               while (curr != source) {
                  flow[prev[curr]][curr] += addFlow;
                  flow[curr][prev[curr]] -= addFlow;
                  curr = prev[curr];
               }
               maxFlow += addFlow;
             }
          }
       }
       return maxFlow;
    }
};

int main()
{
    ifstream in ("harta.in");
    ofstream out ("harta.out");

    MaxFlow flow; in >> flow.V;
    flow.source = 0, flow.sink = 2 * flow.V + 1;
    for (int node = 1; node <= flow.V; node ++) {
       int indeg, outdeg; in >> indeg >> outdeg;
       flow.add_edge (flow.source, node, indeg);
       flow.add_edge (node + flow.V, flow.sink, outdeg);
    }
    for (int first = 1; first <= flow.V; first ++)
       for (int second = flow.V + 1; second <= 2 * flow.V; second ++)
          if (first != second - flow.V)
            flow.add_edge (first, second, 1);
    flow.solve ();

    vector<pair<int, int>> answer;
    for (int first = 1; first <= flow.V; first ++)
       for (int second = flow.V + 1; second <= 2 * flow.V; second ++)
          if (flow.flow[first][second])
            answer.push_back ({first, second - flow.V});

    out << answer.size () << "\n";
    for (pair<int, int> x : answer)
       out << x.first << " " << x.second << "\n";
    return 0;
}