Pagini recente » Cod sursa (job #1388094) | Cod sursa (job #618960) | Cod sursa (job #1424608) | Cod sursa (job #2058373) | Cod sursa (job #3193881)
//logica avem n noduri cele originale si n copii.
//din start plecam cu ce vrea sa iasa din nod
//in t venim cu vrea sa intre in nod
//si asa se rezolva (e prea mistoo)
#include <iostream>
#include <vector>
#include <queue>
#include <climits>
#include <fstream>
using namespace std;
struct Edge{
int node;
int flow;
int capacity;
int reverse; //stores an index of reverse edge
};
class Graf {
int Nodes;
int* level;
vector<Edge>* adj;
public:
Graf(int Nodes){
adj = new vector<Edge>[Nodes];
this->Nodes = Nodes;
level = new int[Nodes];
}
void adaugare_muchie(int node1, int node2, int cost){
Edge a{node2, 0, cost, (int)adj[node2].size() };
//reverse edge
Edge b{node1, 0, 0, (int)adj[node1].size() };
adj[node1].push_back(a);
adj[node2].push_back(b);//reverse edge
}
//functie doar pt aceasta problema
vector<pair<int,int>> get_muchii(int start, int finish){
vector<pair<int,int>> result;
for(int i = start; i <= finish; i ++){
for(auto &muchie: adj[i]){
if(muchie.flow == 1){
result.push_back(make_pair(i,muchie.node - finish)); //acest -N este specific doar acestei probleme
}
}
}
return result;
}
bool BFS(int s, int t);
int DFSFlow(int s, int flow, int t, int ptr[]);
int MaxFlowDinic(int s, int t);
};
bool Graf::BFS(int s, int t){
for(int i = 0; i < Nodes; i ++){
level[i] = -1;
}
level[s] = 0; //nivelul de start e 0
queue<int> q;
q.push(s);
while(!q.empty()){
int current = q.front();
q.pop();
//mergem prin vecinii nodului curent
for(auto i = adj[current].begin(); i != adj[current].end(); i ++){
Edge& vecin = *i; //se preia vecinul
//verificam daca am mai trecut prin el si daca nu este terminat
if(level[vecin.node] < 0 && vecin.flow < vecin.capacity){
level[vecin.node] = level[current] + 1;
q.push(vecin.node);
}
}
}
//daca nu putem ajunge la sink (t) returnam fals
return level[t] < 0 ? false : true;
}
//un dfs folosit dupa ce se afla nivelul cu BFS.
int Graf::DFSFlow(int node, int flow, int t, int start[]){
if(node == t) return flow;
for(; start[node] < adj[node].size(); start[node]++){
Edge& next = adj[node][start[node]];
//daca mergem inainte cu DFS-ul si muchia nu e terminata
if(level[next.node] == level[node] + 1 && next.flow < next.capacity){
//aflam flowul minim de la node la sink (t)
int curr_flow = min(flow, next.capacity - next.flow);
int temp_flow = DFSFlow(next.node, curr_flow, t, start);
if(temp_flow > 0){
//dupa ce aflam valoarea maxima care o putem duce din node in t
//punem in toate drumurile pana acolo
next.flow += temp_flow;
adj[next.node][next.reverse].flow -= temp_flow;
return temp_flow;
}
}
}
return 0;
}
//aici se vor schimba si valorile din vector<Edge>.
int Graf::MaxFlowDinic(int s, int t){
if( s == t)return - 1;
int total = 0;
//facem caclulul de bfs pana cand nu mai putem ajunge la sink(t)
while(BFS(s,t) == true){
int *start = new int[Nodes + 1]{0};
while(int flow = DFSFlow(s, INT_MAX, t, start)){
total+= flow;
}
delete[] start;
}
return total;
}
int main(){
ifstream fin("harta.in");
ofstream fout("harta.out");
int N;
fin >> N;
Graf g(2*N + 3);
//acum punem muchiile de la start la fiecare nod
//punem muchii de la copie la sfarsit
//adaugam muchie de la fiecare nod la copiile afarente
for(int i = 1; i <= N; i ++)
for(int j = N + 1 ; j <= 2*N; j ++)
if(j - N != i)
g.adaugare_muchie(i,j,1);
for(int i = 1; i <= N ; i ++){
int intrare, iesire;
fin >> intrare >> iesire;
//2*N + 1 = s (inceput), 2*N + 1 = t (sfarsit)
g.adaugare_muchie(2*N + 1, i, intrare);
g.adaugare_muchie(i + N, 2*N + 2, iesire);
}
//aici se face fluxul si se returneaza cate muchii au fost folosite
int n = g.MaxFlowDinic(2*N + 1, 2*N + 2);
//apelam functia din graf care ne da muchiile care au fost schimbate
//respectiv muchiile care au flow 1 cu cost 1 din graf
// si care nu au o legatura cu s si t
vector<pair<int,int>> muchii = g.get_muchii(1,N); //este o functie custom doar de pentru aceasta problema
//afisarea rezultatului
fout << n << endl;
for(int i = 0; i < muchii.size(); i ++){
fout << muchii[i].first << " " << muchii[i].second << endl;
}
return 0;
}