Cod sursa(job #3344846)

Utilizator andrei0925Andrei Perdevara andrei0925 Data 6 martie 2026 00:41:38
Problema Taramul Nicaieri Scor 0
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.6 kb
//practic un cuplaj in graf bipartit unde ne facem in primu rand partea cu nodurile out si partea cu nodurile in
// facem un nod S si tragem muchie de la el la toate nodurile din stanga (out), cu costul = nr de aparitii a nodului respectiv
// facem un nod T si tragem muchie de la toate nodurile din dreapta (in), cu costul = nr de aparitii
// tragem toate muchiile dintre cele doua parti inafara de cele de la un nod la el insasi si toate au costul 1
// facem flowul maxim si afisam muchiile cu dintre noduri cu F > 0
#include <fstream>
#include <vector>
#include <queue>
#include <cstring>
#define NMAX 205
#define INF 1e9

using namespace std;
ifstream cin("harta.in");
ofstream cout("harta.out");
int N, S, T, c, C[NMAX][NMAX], F[NMAX][NMAX], level[NMAX], idx[NMAX], in[NMAX], out[NMAX];
vector <int> G[NMAX];

bool bfs()
{
  memset(level, -1, sizeof(level));
  level[S] = 0;
  queue <int> q;
  q.push(S);
  while(q.size())
  {
    int acc = q.front();
    q.pop();

    for(auto e : G[acc])
    {
      if(level[e] == -1 and C[acc][e] - F[acc][e] > 0)
      {
        level[e] = level[acc] + 1;
        q.push(e);
      }
    }
  }
  if(level[T] == -1)
    return false;
  return true;
}

int dfs(int acc, int pushed)
{
  if(acc == T or pushed == 0)
    return pushed;

  for( ; idx[acc] < G[acc].size(); idx[acc]++)
  {
    int e = G[acc][idx[acc]];

    if(level[e] != level[acc] + 1 or C[acc][e] - F[acc][e] <= 0)
      continue;

    int path_flow = dfs( e, min(pushed, C[acc][e] - F[acc][e]));

    if(path_flow == 0)
      continue;

    F[acc][e] += path_flow;
    F[e][acc] -= path_flow;
    return path_flow;
  }
  return 0;
}

int main()
{
  cin >> N;
  S = 0; T = 2 * N + 1;
  for(int i = 1; i <= N; i++)
  {
    cin >> out[i] >> in[i];
    if(out[i])
    {
      G[S].push_back(i);
      G[i].push_back(S);
      C[S][i] = out[i];
    }

    if(in[i])
    {
      int id = N + i;
      G[id].push_back(T);
      G[T].push_back(id);
      C[id][T] = in[i];
    }
  }

  for(int i = 1; i <= N; i++)
  {
    if(out[i])
    {
      for(int j = N + 1; j <= 2 * N; j++)
      {
        if(i != j - N and in[j - N]){
          G[i].push_back(j);
          G[j].push_back(i);
          C[i][j] = 1;
        }
      }
    }
  }

  int ok = 0;
  while(bfs())
  {
    memset(idx, 0, sizeof(idx));
    while(int pushed = dfs(S, INF))
    {
      ok ++;
    }
  }
  for(int i = 1; i <= N; i++)
  {
    for(int j = N + 1; j <= 2 * N; j++)
    {
      if(F[i][j] > 0)
        cout << i << ' ' << j - N << '\n';
    }
  }
  return 0;
}