Pagini recente » Cod sursa (job #2094412) | Cod sursa (job #1669260) | Cod sursa (job #2203253) | Cod sursa (job #121701) | Cod sursa (job #3188292)
//#define LOCAL_TESTING
#include <fstream>
#include <vector>
#include <queue>
#ifdef LOCAL_TESTING
#define in_file "input.txt"
#define out_file "output.txt"
#else
#define in_file "harta.in"
#define out_file "harta.out
#endif
using namespace std;
vector<vector<int>> capacity;
vector<vector<int>> flux;
vector<bool> visited;
vector<int> parent;
void flux_init(size_t size)
{
parent.resize(size, -1);
visited.resize(size);
flux.resize(size, vector<int>(size, 0));
capacity.resize(size, vector<int>(size, 0));
}
bool bfs(int n)
{
queue<int> q;
q.push(2 * n);
visited[2 * n] = true;
while(!q.empty())
{
int node = q.front();
q.pop();
for(int i = 0; i <= 2 * n + 1; i++)
if(!visited[i] && capacity[node][i] - flux[node][i] > 0)
{
q.push(i);
parent[i] = node;
visited[i] = true;
}
}
return visited[2 * n + 1];
}
int get_max_flow(int n)
{
int flux_maxim = 0;
const int t = 2 * n + 1;
while(bfs(n))
{
int min_capacity = 2e9;
int node1 = parent[t];
int node2 = t;
while(node1 != -1)
{
int c = capacity[node1][node2] - flux[node1][node2];
if(c < min_capacity)
min_capacity = c;
node2 = node1;
node1 = parent[node1];
}
node1 = parent[t];
node2 = t;
while(node1 != -1)
{
flux[node1][node2] += min_capacity;
flux[node2][node1] -= min_capacity;
node2 = node1;
node1 = parent[node1];
}
flux_maxim += min_capacity;
for(int j = 0; j <= t; j++)
visited[j] = false;
}
return flux_maxim;
}
int main()
{
ifstream in(in_file);
ofstream out(out_file);
int n;
in >> n;
flux_init(2 * n + 2);
for(int i = 0; i < n; i++)
{
int x, y;
in >> x >> y;
capacity[2 * n][i] = x;
capacity[i + n][2 * n + 1] = y;
for(int j = 0; j < n; j++)
if(i != j)
capacity[i][j + n] = 1;
}
int flux_maxim = get_max_flow(n);
out << flux_maxim << '\n';
for(int i = 0; i < n; i++)
{
for(int j = 0; j < n; j++)
{
if(flux[i][j + n] == 1)
out << i+1 << ' ' << j+1 << '\n';
}
}
in.close(); out.close();
return 0;
}