Cod sursa(job #2327645)

Utilizator PetyAlexandru Peticaru Pety Data 24 ianuarie 2019 19:46:57
Problema Taramul Nicaieri Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.74 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, cost[402][402], f[402][402], t[402], m;
bool viz[402];
vector<int>g[402];
int s = 0, d = 201;

bool bfs () {
  memset(viz, 0, sizeof(viz));
  viz[s] = 1;
  queue<int>q;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    if (u == d)
      continue;
    for (auto v: g[u]) {
      if (cost[u][v] > f[u][v] && !viz[v]) {
        viz[v] = 1;
        q.push(v);
        t[v] = u;
      }
    }
  }
  return viz[d];
}
void flux (int s, int d) {
  int ans = 0;
  while (bfs()) {
    for (int i = 0; i < g[d].size(); i++) {
      int v = g[d][i];
      if (cost[v][d] > f[v][d] && viz[v]) {
        t[d] = v;
        int fmin = 1000000000;
        for (int i = d; i != s; i = t[i])
          fmin = min(fmin, cost[t[i]][i] - f[t[i]][i]);
         for (int i = d; i != s; i = t[i]) {
           f[t[i]][i] += fmin;
           f[i][t[i]] -= fmin;
         }
        ans += fmin;
      }
    }
  }
}

int main()
{
  fin >> n;
  for (int i = 1; i <= n; i++) {
    int a, b;
    fin >> a >> b;
    g[s].push_back(i);
    g[i].push_back(s);
    cost[s][i] = a;
    g[d].push_back(i + n);
    g[i + n].push_back(d);
    cost[i + n][d] = b;
    m += a + b;
  }
  m /= 2;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      if (i != j) {
        g[i].push_back(j + n);
        g[j + n].push_back(i);
        cost[i][j + n] = 1;
      }
  flux(s, d);
  fout << m << "\n";
  for(int i = 1; i <= n; i++){
    for(int j = 1;j <= n; j++) {
      if(cost[i][j + n] == f[i][j + n] && cost[i][j + n])
        fout << i << " " << j << "\n";
      }
    }
  return 0;
}