Pagini recente » Cod sursa (job #2974147) | Cod sursa (job #3270844) | Cod sursa (job #2933047) | Cod sursa (job #1814626) | Cod sursa (job #3188148)
#include<iostream>
#include<fstream>
#include<vector>
#include<queue>
using namespace std;
#define INF 999999
int N, source, target, maxFlow;
vector<vector<int>> adi, capacity, flow; // lista de adiacenta, matrice de capacitate si matrice de flux
vector<int> parinte, degreeIn, degreeOut; // vectori de parinti, graduri de intrare, respectiv iesire ale nodurilor
ifstream fin("harta.in");
ofstream fout("harta.out");
// cautare in latime pentru a gasi drumuri mai bune
int bfs(){
queue<pair<int, int>> q;
q.push({source, INF});
while(!q.empty()){
int node = q.front().first;
int newFlow = q.front().second;
q.pop();
for(int i : adi[node]){
if(parinte[i] == -1 && capacity[node][i] > 0){
parinte[i] = node;
newFlow = min(newFlow, capacity[node][i]);
if(i == target){
return newFlow;
}
q.push({i, newFlow});
}
}
}
return 0;
}
int main()
{
fin >> N;
adi.resize(2 * N + 2);
capacity.resize(2 * N + 2, vector<int>(2 * N + 2, 0));
flow.resize(N + 1);
parinte.resize(2 * N + 2, -1);
degreeIn.resize(N + 1, 0);
degreeOut.resize(N + 1, 0);
for(int i = 1; i <= N; i++){
fin >> degreeOut[i] >> degreeIn[i];
}
source = 0;
target = 2 * N + 1;
// conectez nodul sursa la noduri, capacitatea fiind data de gradul de iesire al nodului
for(int i = 1; i <= N; i++){
adi[source].push_back(i);
adi[i].push_back(source);
capacity[source][i] = degreeOut[i];
}
// conectez nodurile la nodul destinatie, capacitatea fiind data de gradul de intrare al nodului
for(int i = N + 1; i < target; i++){
adi[target].push_back(i);
adi[i].push_back(target);
capacity[i][target] = degreeIn[i - N];
}
// conectez randurile de coloane, capacitatea fiind 1
for(int i = 1; i <= N; i++){
for(int j = N + 1; j < target; j++){
if(i + N == j){
continue;
}
adi[i].push_back(j);
adi[j].push_back(i);
capacity[i][j] = 1;
}
}
// initializare vector parinti
for(int i = 0; i <= target; i++){
parinte[i] = -1;
}
parinte[source] = -2;
// algoritmul Edmonds-Karp
// gasesc cai mai bune si actualizez fluxul pana nu mai gasesc cai mai bune
int c;
while(c = bfs()){
maxFlow = maxFlow + c;
int node = target;
// actualizez capacitatile de-a lungul caii mai bune
while(node != source){
int stramos = parinte[node];
capacity[stramos][node] -= c;
capacity[node][stramos] += c;
// actualizez matricea de flux pentru muchii directe si indirecte
if(node > source && node < target && stramos > source && stramos < target){
// daca muchia e directa, o adaug
if(stramos < node){
flow[stramos].push_back(node);
}
// daca muchia e indirecta, o sterg
else{
for(int i = 0; i < flow[node].size(); i++){
if(flow[node][i] == stramos){
flow[node].erase(flow[node].begin() + i);
break;
}
}
}
}
node = stramos;
}
// reinitializez vectorul de parinti pentru urmatoarea iteratie
for(int i = 0; i <= target; i++){
parinte[i] = -1;
}
parinte[source] = -2;
}
// afisez fluxul maxim si muchiile fluxului rezultat
fout << maxFlow << "\n";
for(int i = 1; i <= N; i++){
for(int j : flow[i]){
fout << i << " " << j - N << "\n";
}
}
return 0;
}