Pagini recente » Cod sursa (job #654506) | Cod sursa (job #2636767) | Cod sursa (job #205926) | Cod sursa (job #2808870) | Cod sursa (job #3193497)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
using namespace std;
int bfs(int source, int sink, vector<int>& parent,vector<vector<int>>& adjList, vector<vector<int>>& capacity, vector<vector<int>>& flow)
{
fill(parent.begin(), parent.end(), -1);
parent[source] = source;
queue<pair<int, int>> q;
q.push({source, INT_MAX});
while (!q.empty())
{
int currentNode = q.front().first;
int currentFlow = q.front().second;
q.pop();
for (int neighbor : adjList[currentNode])
{
if (parent[neighbor] == -1 && capacity[currentNode][neighbor] > flow[currentNode][neighbor])
{
parent[neighbor] = currentNode;
int newFlow = min(currentFlow, capacity[currentNode][neighbor] - flow[currentNode][neighbor]);
if (neighbor == sink)
{
return newFlow;
}
q.push({neighbor, newFlow});
}
}
}
return 0;
}
int maxFlow(int n, int source, int sink, vector<vector<int>>& adjList,vector<vector<int>>& capacity, vector<vector<int>>& flow)
{
vector<int> parent(n * 2 + 2);
int maxFlow = 0;
int newFlow;
while (newFlow = bfs(source, sink, parent, adjList, capacity, flow))
{
maxFlow = maxFlow + newFlow;
int currentNode = sink;
while (currentNode != source)
{
int previousNode = parent[currentNode];
flow[previousNode][currentNode] = flow[previousNode][currentNode] + newFlow;
flow[currentNode][previousNode] = flow[currentNode][previousNode] - newFlow;
currentNode = previousNode;
}
}
return maxFlow;
}
int main()
{
ifstream f1 ("harta.in");
ofstream f2 ("harta.out");
int n;
f1 >> n;
int source = 0;
int sink = n * 2 + 1;
vector<vector<int>> adjList(n * 2 + 2, vector<int>(n * 2 + 2, 0));
vector<vector<int>> capacity(n * 2 + 2, vector<int>(n * 2 + 2, 0));
vector<vector<int>> flow(n * 2 + 2, vector<int>(n * 2 + 2, 0));
for (int i = 1; i <= n; i++)
{
int outDegree, inDegree;
f1 >> outDegree >> inDegree;
adjList[source].push_back(i);
adjList[i].push_back(source);
capacity[source][i] = outDegree;
adjList[sink].push_back(i + n);
adjList[i+n].push_back(sink);
capacity[i + n][sink] = inDegree;
}
for(int i = 1; i <= n ; i++)
for(int j = 1 ; j <= n ; j++)
if(i != j)
{
adjList[i].push_back(j + n);
adjList[j+n].push_back(i);
capacity[i][j+n] = 1;
}
f2<<maxFlow(n,source,sink,adjList,capacity,flow)<<endl;
for(int i = 1 ; i <= n ; i++)
for(int j = n + 1 ; j <= n+n ; j++)
if(flow[i][j])
f2<<i<<" "<<j-n<<endl;
return 0;
}