Pagini recente » Clasament 123345 | Cod sursa (job #39154) | Cod sursa (job #392255) | Cod sursa (job #2932886) | Cod sursa (job #2961415)
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <climits>
#include <cstring>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int N, M;
vector <vector<int>> adj, capacity;
vector <int> parent;
vector <bool> vis;
bool BFS()
{
for (int i = 0; i <= 2*N+1; i++)
{
parent[i] = 0;
vis[i] = false;
}
parent[0] = -1;
vis[0] = true;
queue <int> q;
q.push(0);
while (!q.empty())
{
int current = q.front();
q.pop();
if (current == 2 * N + 1)
return 1;
for (int next : adj[current])
{
if (!vis[next] && capacity[current][next])
{
parent[next] = current;
vis[next] = true;
q.push(next);
}
}
}
return false;
}
int MaxFlow(int start, int end)
{
long max_flow = 0; //initializam fluxul maxim pe care il calculam
while (BFS()) //cat timp exista un drum prin care putem ajunge din nodul de start in nodul destinatie
{
for (auto x : adj[2 * N + 1])
{
if (capacity[x][2 * N + 1] > 0 && vis[x])
{
int flow = capacity[x][2 * N + 1], u, v;
for (int node = end; node != start; node = parent[node])
flow = min(flow, capacity[parent[node]][node]);
for (int node = end; node != start; node = parent[node])
{
capacity[parent[node]][node] -= flow;
capacity[node][parent[node]] += flow;
}
max_flow += flow;
}
}
}
return max_flow;
}
int main()
{
fin >> N;
adj.resize(2 * N + 5);
parent.resize(2 * N + 5, 0);
vis.resize(2 * N + 5, false);
capacity.resize(2 * N + 5, vector <int>(2 * N + 5));
for (int i = 1; i <= N; i++)
for (int j = 1; j <= N; j++)
if (i != j)
{
adj[i].push_back(j + N);
adj[j + N].push_back(i);
capacity[i][j + N] = 1;
}
int in, out;
for (int i = 1; i <= N; i++)
{
fin >> in >> out;
adj[0].push_back(i);
adj[i].push_back(0);
capacity[0][i] = in;
adj[2 * N + 1].push_back(i + N);
adj[i + N].push_back(2 * N + 1);
capacity[i + N][2 * N + 1] = out;
}
int maxFlow = MaxFlow(0, 2 * N + 1);
fout << maxFlow << endl;
for (int i = 1; i <= N; i++)
for (int j = N + 1; j <= 2 * N; j++)
if (capacity[j][i] == 1)
fout << i << " " << j - N << '\n';
return 0;
}