Pagini recente » Cod sursa (job #1429080) | Cod sursa (job #2396051) | Cod sursa (job #2076329) | Cod sursa (job #2394987) | Cod sursa (job #2960646)
#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <fstream>
using namespace std;
class Flow {
struct Edge {
int from, to;
int cf;
Edge(int from = 0, int to = 0, int cf = 0) : from(from), to(to), cf(cf) {}
};
int n, m;
int source, destination;
// adjList[i] = indicii muchiilor care pornesc din nodul i
vector<vector<int>> adjList;
vector<Edge> edges;
// dad[i] = indicele muchiei parinte din arborele BFS
vector<int> dad;
// adauga flux in drumul de ameliorare care se termina in nodul dat ca parametru si intoarce valoarea fluxului adaugat
int addFlow(int node) {
int canAdd = -1; // fluxul maxim pe care il pot adauga pe drumul de ameliorare curent
int crt = node;
while(crt != source) {
if(canAdd == -1 || edges[dad[crt]].cf < canAdd)
canAdd = edges[dad[crt]].cf;
crt = edges[dad[crt]].from;
}
// parcurg din nou drumul de ameliorare ca sa adaug noul flux
crt = node;
while(crt != source) {
edges[dad[crt]].cf -= canAdd;
edges[dad[crt] ^ 1].cf += canAdd;
crt = edges[dad[crt]].from;
}
return canAdd;
}
// creeaza arborele BFS prin vectorul de tati si intoarce daca a gasit macar un drum de ameliorare sau nu
bool bfs() {
bool reachedDestination = false; // daca am ajuns la destinatie printr-un drum de ameliorare
queue<int> q;
q.push(source);
for(int i = 1; i <= n; i++)
dad[i] = -1;
while(!q.empty()) {
int node = q.front();
q.pop();
for(int edgeIdx: adjList[node]) {
int ngh = edges[edgeIdx].to;
// caut muchii in care mai pot adauga flux si care ajung in noduri nevizitate
if(ngh == source || dad[ngh] != -1 || edges[edgeIdx].cf == 0)
continue;
// daca am ajuns la destinatie nu memorez nodul din care am ajuns pentru ca pot avea mai multe drumuri
if(ngh == destination) {
reachedDestination = true;
continue;
}
dad[ngh] = edgeIdx;
q.push(ngh);
}
}
return reachedDestination;
}
public:
void init(int n, int source = 1, int destination = -1) {
this->n = n;
this->source = source;
this->destination = destination == -1 ? n : destination;
adjList.resize(n + 1);
dad.resize(n + 1);
}
// adauga muchia (from, to) in retea; indicele muchiei va fi pe o pozitie para, iar muchia inversa va fi pe urmatoarea pozitie
void addEdge(int from, int to, int capacity) {
edges.push_back(Edge(from, to, capacity));
adjList[from].push_back(edges.size() - 1);
// adaug si muchia inversa de capacitate 0
edges.push_back(Edge(to, from, 0));
adjList[to].push_back(edges.size() - 1);
}
// intoarce fluxul maxim din retea
int maxFlow() {
int maxFlow = 0;
// cat timp exista drumuri de ameliorare mai putem adauga flux
while(bfs())
for(int edgeIdx: adjList[destination]) {
int node = edges[edgeIdx].to;
// conectam pe rand nodul destinatie la toate nodurile din care se poate ajunge in acesta si care sunt capatul unui drum de ameliorare
if((node == source || dad[node] != -1) && edges[edgeIdx ^ 1].cf > 0) {
dad[destination] = edgeIdx ^ 1;
maxFlow += addFlow(destination);
}
}
return maxFlow;
}
vector<pair<int, int>> getEdges() {
vector<pair<int, int>> ret;
for(int i = 0; i < edges.size(); i += 2)
if(edges[i].cf == 0 && edges[i].from != source && edges[i].to != destination)
ret.push_back({ edges[i].from, edges[i].to });
return ret;
}
};
int n;
void read(Flow &flow) {
ifstream fin("harta.in");
int in, out, source, destination;
fin >> n;
source = 0;
destination = 2 * n + 1;
flow.init(2 * n + 2, source, destination);
for(int i = 1; i <= n; i++) {
fin >> out >> in;
// adaug muchii de la sursa la fiecare nod cu capacitatea egala cu gradul de iesire,
// intrucat cantitatea de flux care va iesi din nod este data de numarul de muchii care ies din el
flow.addEdge(source, i, out);
// adaug muchii de la fiecare nod la destinatie cu capacitatea egala cu gradul de intrare
// intrucat cantitatea de flux care intra in nod este data de numarul de muchii care intra in el
flow.addEdge(n + i, destination, in);
}
// adaug muchii intre fiecare 2 noduri diferite de capacitate 1
// dintre aceste muchii vor fi selectate cele prin care va trece flux
for(int i = 1; i <= n; i++)
for(int j = 1; j <= n; j++)
if(i != j)
flow.addEdge(i, n + j, 1);
}
int main() {
Flow flow;
read(flow);
int edgesCount = flow.maxFlow();
ofstream fout("harta.out");
fout << edgesCount << '\n';
vector<pair<int, int>> edges = flow.getEdges();
for(pair<int, int> edge: edges)
fout << edge.first << ' ' << (edge.second > n ? edge.second - n : edge.second) << '\n';
return 0;
}