Pagini recente » Cod sursa (job #2808345) | Cod sursa (job #2623615) | Cod sursa (job #38482) | Cod sursa (job #3130671) | Cod sursa (job #3190456)
#include <iostream>
#include <queue>
#include <vector>
#include <climits>
#include <fstream>
using namespace std;
const int UNVISITED = -1;
const int SOURCE = -2;
const int INF = INT_MAX;
int n;
vector<vector<int>> capacity;
vector<vector<int>> flow;
vector<vector<int>> adj;
vector<int> parent;
int bfs(int source, int target)
{
for (int i = 0; i <= 2 * n + 1; ++i)
parent[i] = -1;
parent[source] = SOURCE;
queue<pair<int, int>> q;
q.push({source, INF});
while (!q.empty())
{
int cur = q.front().first;
int prevFlow = q.front().second;
q.pop();
for (int next : adj[cur])
{
if (parent[next] == UNVISITED && capacity[cur][next] > flow[cur][next])
{
parent[next] = cur;
int residualFlow = capacity[cur][next] - flow[cur][next];
int minimumFlow = min(residualFlow, prevFlow);
if (next == target)
return minimumFlow;
q.push({next, minimumFlow});
}
}
}
return 0;
}
void maxflow(int s, int t)
{
int newFlow;
parent.resize(2 * n + 2);
while (newFlow = bfs(s, t))
{
int cur = t;
while (cur != s)
{
int prev = parent[cur];
flow[prev][cur] -= newFlow;
flow[cur][prev] += newFlow;
cur = prev;
}
}
}
ifstream fin("harta.in");
ofstream fout("harta.out");
int main()
{
fin >> n;
int source = 0, target = 2 * n + 1;
int paths = 0;
capacity.resize(2 * n + 2, vector<int>(2 * n + 2));
flow.resize(2 * n + 2, vector<int>(2 * n + 2));
adj.resize(2 * n + 2);
// starting from 1 as 0 will be the source node
for (int i = 1; i <= n; i++)
{
int x, y;
// x - out degree, y - in degree
fin >> x >> y;
paths += x;
capacity[source][i] = x;
capacity[n + i][target] = y;
adj[source].push_back(i);
adj[i].push_back(source);
adj[n + i].push_back(target);
adj[target].push_back(n + i);
for (int j = 1; j <= n; ++j)
{
if (i != j)
{
capacity[i][n + j] = 1;
adj[i].push_back(n + j);
adj[n + j].push_back(i);
}
}
}
maxflow(source, target);
fout << paths << '\n';
for (int i = 1; i <= n; ++i)
for (int j = n + 1; j <= 2 * n; ++j)
if (flow[i][j])
fout << i << ' ' << j - n << '\n';
return 0;
}