Cod sursa(job #1554496)

Utilizator vladrochianVlad Rochian vladrochian Data 21 decembrie 2015 13:36:23
Problema Taramul Nicaieri Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.97 kb
#include <cstring>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;

const int N_MAX = 100;
const int NODES = 2 * N_MAX + 2;
const int INF = 1e9;

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

int N, dest, cnt;
vector<int> al[NODES];

bool use[NODES];
int padre[NODES];

int capacity[NODES][NODES];
int flow[NODES][NODES];

inline void AddEdge(int x, int y, int c) {
   al[x].push_back(y);
   al[y].push_back(x);
   capacity[x][y] = c;
}

bool Bfs() {
   memset(use, 0, sizeof use);
   queue<int> q;
   use[0] = true;
   q.push(0);
   while (!q.empty()) {
      int node = q.front();
      q.pop();
      if (node == dest)
         continue;
      for (int son : al[node])
         if (!use[son] && flow[node][son] < capacity[node][son]) {
            padre[son] = node;
            use[son] = true;
            q.push(son);
         }
   }
   return use[dest];
}

int main() {
   fin >> N;
   dest = 2 * N + 1;
   for (int i = 1; i <= N; ++i) {
      int out, in;
      fin >> out >> in;
      AddEdge(0, i, out);
      AddEdge(N + i, dest, in);
      cnt += out;
   }
   for (int i = 1; i <= N; ++i)
      for (int j = 1; j <= N; ++j)
         if (i != j)
            AddEdge(i, N + j, 1);

   while (Bfs()) {
      for (int node : al[dest])
         if (use[node] && flow[node][dest] < capacity[node][dest]) {
            padre[dest] = node;
            bool ok = true;
            for (int i = dest; i != 0; i = padre[i])
               if (flow[padre[i]][i] == capacity[padre[i]][i])
                  ok = false;
            if (ok)
               for (int i = dest; i != 0; i = padre[i]) {
                  ++flow[padre[i]][i];
                  --flow[i][padre[i]];
               }
         }
   }

   fout << cnt << "\n";
   for (int i = 1; i <= N; ++i)
      for (int j = 1; j <= N; ++j)
         if (flow[i][N + j] == 1)
            fout << i << " " << j << "\n";
   return 0;
}