Pagini recente » Cod sursa (job #688409) | Cod sursa (job #306555) | Cod sursa (job #411216) | Cod sursa (job #2339235) | Cod sursa (job #2955309)
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
int root, dest, n, m, d1, d2, c, total, l, r;
int tati[202];
vector<vector<int>>lista;
int flux[202][202];
int label[202];
ifstream f("harta.in");
ofstream g("harta.out");
bool BFS() {
queue<int>q;
for (int i = 0; i <= 2*n+1; i++)
{
tati[i] = -1;
label[i] = 0;
}
label[0] = 1;
q.push(0);
while (!q.empty()) {
int x = q.front();
q.pop();
for (auto el : lista[x]) {
if (label[el] == 0 && flux[x][el] > 0) {
tati[el] = x;
q.push(el);
label[el] = 1;
if (el == 2*n+1) {
return 1;
}
}
}
}
return 0;
}
int main() {
f >> n;
lista.resize(2*n + 2);
for (int i = 1; i <= n; i++)
{
f >> d1 >> d2;
flux[0][i] = d1;
flux[n+i][2*n + 1] = d2;
lista[0].push_back(i);
lista[i].push_back(0);
lista[n + i].push_back(2 * n + 1);
lista[2 * n + 1].push_back(n + i);
for (int j = n + 1; j <= 2 * n; j++)
{
if (j - i == n)
continue;
lista[i].push_back(j);
lista[j].push_back(i);
flux[i][j] = 1;
}
}
while (BFS()) {
for (auto el : lista[n])
{
if (!label[el])
continue;
int min1 = 10000000;
int v = 2*n+1;
while (v != 0)
{
min1 = min(min1, flux[tati[v]][v]);
v = tati[v];
}
v = 2*n+1;
while (v != 0) {
flux[tati[v]][v] -= min1;
flux[v][tati[v]] += min1;
v = tati[v];
}
total = total + min1;
}
}
g << total << "\n";
for(int i=1;i<=n;i++)
for(int j=n+1;j<=2*n+1;j++)
if (flux[j][i] == 1) {
g << i << " " << j - n << "\n";
continue;
}
}