Pagini recente » Cod sursa (job #258440) | Cod sursa (job #1985843) | Cod sursa (job #93350) | Cod sursa (job #9585) | Cod sursa (job #3190740)
#include <bits/stdc++.h>
using namespace std;
class Graph {
private:
vector<vector<int>> adjList;
vector<unordered_map<int, int>> capacity, flow;
vector<int> parent;
int BFS(int start, int finish);
public:
// Constructori
Graph(int size){
adjList.resize(size + 5);
capacity.resize(size + 5);
flow.resize(size + 5);
parent.resize(size + 5);
}
// Getters & Setters
vector<unordered_map<int, int>> getFlow(){ return this->flow; }
vector<unordered_map<int, int>> getCapacity(){ return this->capacity; }
// Metode
void add(int x, int y, int capacity){
this->adjList[x].push_back(y);
this->adjList[y].push_back(x);
this->capacity[x][y] = capacity;
}
int maxFlow(int start, int finish);
};
int Graph::BFS(int start, int finish){
fill(this->parent.begin(), this->parent.end(), -1);
this->parent[start] = -2;
queue<pair<int, int>> q;
q.push({start, INT_MAX});
while(!q.empty()){
int curr = q.front().first;
int flow = q.front().second;
q.pop();
for(int next : this->adjList[curr]){
if(this->parent[next] == -1 && this->capacity[curr][next] > this->flow[curr][next]){
this->parent[next] = curr;
int newFlow = min(flow, this->capacity[curr][next] - this->flow[curr][next]);
if(next == finish){
return newFlow;
}
q.push({next, newFlow});
}
}
}
return 0;
}
int Graph::maxFlow(int start, int finish){
int flow = 0;
while(true){
int newFlow = BFS(start, finish);
if(newFlow == 0){
break;
}
flow += newFlow;
int curr = finish;
while(curr != start){
int prev = this->parent[curr];
this->flow[prev][curr] += newFlow;
this->flow[curr][prev] -= newFlow;
curr = prev;
}
}
return flow;
}
class Solution {
public:
void Harta(){
ifstream fin("harta.in");
ofstream fout("harta.out");
int n, nrMuchii = 0;
fin >> n;
int s = 0, t = 2 * n + 1;
Graph Graf(t);
for(int i = 1; i <= n; ++i){
int x, y;
fin >> x >> y;
nrMuchii += x;
for(int j = 1; j <= n; ++j){
if(j != i){
Graf.add(i, j + n, 1);
}
}
Graf.add(s, i, x);
Graf.add(i + n, t, y);
}
Graf.maxFlow(s, t);
fout << nrMuchii << "\n";
for(int i = 1; i <= n; ++i){
for(int j = n + 1; j < t; ++j){
if(Graf.getFlow()[i][j]){
fout << i << " " << j - n << "\n";
}
}
}
}
};
int main(){
Solution s;
s.Harta();
return 0;
}