Pagini recente » Cod sursa (job #2005363) | Cod sursa (job #636281) | Cod sursa (job #1192849) | Cod sursa (job #1057371) | Cod sursa (job #3186343)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <limits.h>
#include <queue>
using namespace std;
const int N = 105;
ifstream fin("harta.in");
ofstream fout("harta.out");
int n, src, dst;
vector<int> g[2 * N];
vector<bool> vizitat;
int capacitate[2 * N][2 * N], flow[2 * N][2 * N], t[2 * N];
void bfs()
{
vizitat.assign(dst + 1, false);
queue<int> q;
q.push(src);
vizitat[src] = true;
t[src] = 0;
while (!q.empty())
{
int current = q.front();
q.pop();
if (current == dst)
{
continue;
}
for (int next : g[current])
{
if (!vizitat[next] && capacitate[current][next] != flow[current][next])
{
vizitat[next] = true;
t[next] = current;
q.push(next);
}
}
}
}
int main()
{
fin >> n;
src = 0;
dst = 2 * n + 1;
int totalMuchii = 0;
for (int i = 1; i <= n; i++)
{
int out, in;
fin >> out >> in;
totalMuchii += in;
capacitate[src][i] = out;
capacitate[n + i][dst] = in;
g[src].push_back(i);
g[i].push_back(src);
g[n + i].push_back(dst);
g[dst].push_back(n + i);
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (i != j)
{
capacitate[i][n + j] = 1;
g[i].push_back(n + j);
g[n + j].push_back(i);
}
}
}
// flux
while (true)
{
bfs();
if (vizitat[dst] == false)
{
break;
}
// ia in calcul toate lanturile
for (int next : g[dst])
{
if (vizitat[next] == false || capacitate[next][dst] == flow[next][dst])
{
continue;
}
t[dst] = next;
int minFlow = INT_MAX;
for (int nod = dst; nod != src; nod = t[nod])
{
minFlow = min(minFlow, capacitate[t[nod]][nod] - flow[t[nod]][nod]);
}
if (minFlow == 0)
{
continue;
}
for (int nod = dst; nod != src; nod = t[nod])
{
flow[t[nod]][nod] += minFlow;
flow[nod][t[nod]] -= minFlow;
}
}
}
fout << totalMuchii << '\n';
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
if (i != j && capacitate[i][n + j] == flow[i][n + j])
{
fout << i << ' ' << j << '\n';
}
}
}
return 0;
}
/*
OBS:
- impartim in 2 multimi de n elemente
- conectam primele n varfuri la sursa cu capacitate = muchii_iesire
- conectam ultimele n varfuri la destinatie cu capacitate = muchii_intrare
- conectam primele n varfuri la ultimele n varfuri cu capacitate = 1 (nu conectam nodul la el insusi => [i != n + i]) => simulam ce varfuri conectam
- aplicam Edmonds-Karp
*/