Pagini recente » Cod sursa (job #605970) | Cod sursa (job #544497) | Cod sursa (job #1100987) | Cod sursa (job #2157193) | Cod sursa (job #2957468)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int BFS(int& n, int& source, int& target, vector<vector<int>>& capacity, vector<int>& parent)
{
vector<bool> visited(n+1, false);
queue<pair<int, int>> bfs_q;
bfs_q.push({source, INT_MAX});
visited[source] = true;
int min_flow;
while(!bfs_q.empty())
{
int curr_v = bfs_q.front().first;
int curr_flow = bfs_q.front().second;
bfs_q.pop();
for(int next = 1; next < n; next++)
if(!visited[next] && capacity[curr_v][next] > 0)
{
visited[next] = true;
min_flow = min(curr_flow, capacity[curr_v][next]);
parent[next] = curr_v;
if(next == target)
{
return min_flow;
}
bfs_q.push({next, min_flow});
}
}
return 0;
}
int main()
{
int n, flow, source, target, size;
fin >> n;
size = 2*n + 2;
vector<vector<int>> capacity(size, vector<int>(size));
vector<int> parent(size, -1);
flow = 0;
source = 0;
target = size-1;
for(int i = 1; i <= n; i++)
{
int in, out;
fin >> out >> in;
capacity[source][i] = out;
capacity[i+n][target] = in;
for(int j = n+1; j <= 2*n; j++)
if(i+n != j)
capacity[i][j] = 1;
}
while(true)
{
int min_flow = BFS(size, source, target, capacity, parent);
if(min_flow == 0)
break;
flow += min_flow;
for(auto curr_v = target; curr_v != source; curr_v = parent[curr_v])
{
capacity[parent[curr_v]][curr_v] -= min_flow;
capacity[curr_v][parent[curr_v]] += min_flow;
}
}
fout << flow << '\n';
for(int i = 1; i <= n; i++)
for(int j = n+1; j < size; j++)
if(capacity[i][j] == 0 && capacity[j][i] == 1)
fout << i << " " << j - n << '\n';
return 0;
}