Pagini recente » Istoria paginii runda/4-aprilie_preoni-cl._5-8/clasament | Cod sursa (job #1923621) | Cod sursa (job #1015574) | Cod sursa (job #1184719) | Cod sursa (job #2960214)
#include <bits/stdc++.h>
#define dim 220
#define inf INT_MAX
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int tata[dim], a[dim][dim], gradin[dim], gradout[dim], n, m, nod, flow, maxFlow;
bool viz[dim];
///algoritmul clasic de bfs pt max flow doar ca in loc de t am 2n+1
bool bfs()
{
queue<int> coada;
///initializam vectorul de tati cu 0, iar cel de viz cu false
memset(tata, 0, sizeof(tata));
memset(viz, false, sizeof(viz));
coada.push(0);
viz[0] = true;
tata[0] = -1;
while (!coada.empty())
{
int node = coada.front();
coada.pop();
if (node == 2 * n + 1)
return true;
for (int i = 1; i <= 2 * n + 1; i++)
{
if (!viz[i] && a[node][i] > 0)
{
coada.push(i);
viz[i] = true;
tata[i] = node;
}
}
}
return false;
}
void citireDate()
{
f >> n;
for (int i = 1; i <= n; i++)
{
f >> gradout[i] >> gradin[i];
///adaugam un nou start si un nou final(cu muchii de capacitati egale cu gradele out, respectiv in),
///si dublam nodurile, ca sa-l putem lega pe fiecare cu fiecare
///2n+1 fiind t-ul
a[0][i] = gradout[i];
a[n + i][2 * n + 1] = gradin[i];
for (int j = 1; j <= n; j++)
if (i != j)
a[i][n + j] = 1;
}
}
void reglamFlow()
{
while (bfs())
{
for (int i = 1; i <= n; i++)
{
///daca a fost vizitat si daca a ajuns la destinatie
if (viz[n + i] && a[n + i][2 * n + 1] > 0) {
flow = inf;
tata[2 * n + 1] = n + i;
///parcurgem lantul de la T la S si luam minimul(iP)
for (nod = 2 * n + 1; nod != 0; nod = tata[nod])
flow = min(flow, a[tata[nod]][nod]);
if (flow == 0)
continue;
///reglam flow-ul
for (nod = 2 * n + 1; nod != 0; nod = tata[nod])
{
a[tata[nod]][nod] -= flow;
a[nod][tata[nod]] += flow;
}
///adaugam iP ul la flow ul total
maxFlow += flow;
}
}
}
}
int main() {
citireDate();
reglamFlow();
g << maxFlow << '\n';
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
if (a[i][n + j] == 0 && i != j)
g << i << " " << j << '\n';
}
return 0;
}