Pagini recente » Cod sursa (job #2305179) | Cod sursa (job #645782) | pentru-cei-mici | Cod sursa (job #3284663) | Cod sursa (job #2966956)
//Ford Fulkerson Algorithm Edmonds Karp Algorithm For Max Flow
//O(VE^2)
#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int N, source, sink, maxflow;
vector<vector <int>> graph;
vector<bool> visited;
vector<int> parent;
vector<vector<int>> capacity;
bool bfs () {
fill(visited.begin(), visited.end(), false);
queue<int> q;
visited[source] = true;
parent[source] = -1;
q.push(source);
while (!q.empty()) {
int nod_curent = q.front();
q.pop();
for (auto i: graph[nod_curent]) {
if (!visited[i] && capacity[nod_curent][i]) {
parent[i] = nod_curent;
if (i == sink){
return true;
}
visited[i] = true;
q.push(i);
}
}
}
return false;
}
int getMaxFlow(){
while(bfs()){
int minflow = 1e9;
int aux = sink;
while(aux)
{
minflow = min(capacity[parent[aux]][aux], minflow);
aux = parent[aux];
}
aux = sink;
while(aux)
{
capacity[parent[aux]][aux] -= minflow;
capacity[aux][parent[aux]] += minflow;
aux = parent[aux];
}
maxflow += minflow;
}
return maxflow;
}
int main ()
{
f>>N;
source = 0;
sink = 2*N+1;
graph.resize(sink+1);
visited.resize(sink+1);
capacity.resize(sink+1, vector<int>(sink+1, 0));
parent.resize(sink+1,-1);
for (int i=1; i<=N; i++)
for (int j =1+N; j<=2*N; j++) {
if (i != j-N)
{
graph[i].push_back(j);
graph[j].push_back(i);
graph[source].push_back(i);
graph[i].push_back(source);
graph[sink].push_back(i+N);
graph[i+N].push_back(sink);
capacity[i][j] = 1;
}
}
for (int i=1; i<=N; i++) {
int val1, val2;
f >> val1 >> val2;
capacity[source][i] = val1;
capacity[i+N][sink] = val2;
}
g << getMaxFlow() << "\n";
for (int i=1; i<=N; i++)
for (int j=1+N; j<=2*N; j++){
if (capacity[j][i]) {
g << i << " " << j - N << "\n";
}
}
return 0;
}