Pagini recente » Cod sursa (job #750552) | Cod sursa (job #2129178) | Cod sursa (job #2894440) | Cod sursa (job #1791832) | Cod sursa (job #3187984)
#include <iostream>
#include <vector>
#include <queue>
#include <limits.h>
#include <fstream>
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
struct Edge{
int destination;
int capacity;
int flow;
int residual;
Edge(int v, int c){
destination = v;
capacity = c;
flow = 0;
residual = capacity;
}
};
class Graph{
int V;
vector< vector<Edge> > adj;
public:
Graph(const int& V){
this->V = V;
adj = vector< vector<Edge> >(V+2);
}
void AddEdge(const int& u, const int& v, const int& c){
Edge e_u(v,c);
Edge e_v(u,0);
adj[u].push_back(e_u);
adj[v].push_back(e_v);
}
int EdmondsKarp(int source, int sink) {
int maxFlow = 0;
while (true) {
vector<int> parent(V+2, -1);
queue<pair<int, int>> q;
q.push({source, INT_MAX});
while (!q.empty()) {
int u = q.front().first;
int minCapacity = q.front().second;
q.pop();
for (const Edge& e : adj[u]) {
int v = e.destination;
if (parent[v] == -1 && e.residual > 0) {
parent[v] = u;
// Actualizăm capacitatea minimă pe drum
int newMinCapacity = min(minCapacity, e.residual);
q.push({v, newMinCapacity});
if (v == sink) {
int pathFlow = newMinCapacity;
int current = v;
while (current != source) {
int previous = parent[current];
for (Edge& edge : adj[previous]) {
if (edge.destination == current) {
edge.residual -= pathFlow;
edge.flow += pathFlow;
break;
}
}
for (Edge& reverseEdge : adj[current]) {
if (reverseEdge.destination == previous) {
reverseEdge.residual += pathFlow;
break;
}
}
current = previous;
}
maxFlow += pathFlow;
break;
}
}
}
}
if (parent[sink] == -1) {
break;
}
}
return maxFlow;
}
void Afisare(){
for(int i=0;i<=V+1;i++)
for(auto e: adj[i])
cout<<i<<" "<<e.destination<<" "<<e.capacity<<" "<<e.flow<<" "<<e.residual<<"\n";
}
void Roads(){
for(int i=1;i<=V/2;i++){
for(auto e : adj[i]){
if(e.residual==0&&e.capacity)
g<<i<<" "<<e.destination-V/2<<endl;
}
}
}
};
int main(){
int N;
f>>N;
int source = 0;
int sink = 2*N+1;
Graph G(2*N);
int out,in;
for(int i=1; i<=N; i++){
f>>out>>in;
G.AddEdge(source,i,out);
G.AddEdge(N+i,sink,in);
for(int j=1;j<=N;j++)
if(i!=j) G.AddEdge(i,N+j,1);
}
g<<G.EdmondsKarp(source,sink)<<endl;
G.Roads();
return 0;
}