Pagini recente » Cod sursa (job #1202182) | Cod sursa (job #1413968) | Cod sursa (job #743440) | Cod sursa (job #2496755) | Cod sursa (job #2961728)
#include <fstream>
#include <vector>
#include <queue>
std::ifstream in("harta.in");
std::ofstream out("harta.out");
const int N = 205, MAX = 1e+7;
int n, maxFlow, grid[N][N];
std::vector<int> vis(N), repr(N);
bool BFS()
{
std::fill(repr.begin(), repr.end(), -1);
std::fill(vis.begin(), vis.end(), 0);
std::queue<int> Q;
Q.push(0);
vis[0] = 1;
while (!Q.empty())
{
int x = Q.front();
Q.pop();
if (x == 2 * n + 1)
return true;
for (int v = 1; v <= 2 * n + 1; v++)
{
if (!grid[x][v] || vis[v])
continue;
Q.push(v);
vis[v] = 1;
repr[v] = x;
}
}
return false;
}
int main()
{
in >> n;
for (int i = 1; i <= n; i++)
{
int x, y;
in >> x >> y;
grid[0][i] = x;
grid[n + i][2 * n + 1] = y;
for (int j = 1; j <= n; j++)
if (i != j)
grid[i][n + j] = 1;
}
/*for (int i = 0; i <= 2 * n + 1; i++)
{
for (int j = 0; j <= 2 * n + 1; j++)
out << grid[i][j] << ' ';
out << '\n';
}*/
out << '\n';
while (BFS())
{
for (int x = n + 1; x < 2 * n + 1; x++)
{
if (!grid[x][2 * n + 1] || !vis[x])
continue;
std::vector<int> path;
path.push_back(x);
int curr = repr[x];
while (curr != 0)
{
path.push_back(curr);
curr = repr[curr];
}
path.push_back(0);
int flow = MAX;
for (int i = path.size() - 1; i >= 1; i--)
flow = std::min(flow, grid[path[i]][path[i - 1]]);
maxFlow += flow;
for (int i = path.size() - 1; i >= 1; i--)
{
grid[path[i]][path[i - 1]] -= flow;
grid[path[i - 1]][path[i]] += flow;
}
}
}
out << maxFlow << '\n';
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
if (i != j && grid[i][n + j] == 0)
out << i << " " << j << '\n';
return 0;
}