Pagini recente » Cod sursa (job #15515) | Cod sursa (job #2780054) | Cod sursa (job #1510592) | Cod sursa (job #3233018) | Cod sursa (job #2961296)
#include <fstream>
#include <iostream>
#include <climits>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
struct edge{
int y;
int capacity;
int flow;
};
int n, x, y;
queue<int> q;
int father[2005];
vector<edge> ad[2005];
int source, destination;
bool explored[2005];
bool cmp(edge e1, edge e2) {
return e1.y < e2.y;
}
int bfs() {
fill(father + 1, father + 2 * n + 3, 0);
fill(explored + 1, explored + 2 * n + 3, 0);
explored[source] = 1;
q.push(source);
while(!q.empty()) {
int node = q.front();
q.pop();
if(node == destination)
continue;
for(auto vec : ad[node]) {
if(vec.flow < vec.capacity && explored[vec.y] == 0) {
explored[vec.y] = 1;
q.push(vec.y);
father[vec.y] = node;
}
}
}
if(explored[destination] == 0)
return 0; // destination can't be reached!
else
return 1; // destination reached!
}
int findPosition(int node, int vec){
int st = 0;
int dr = ad[node].size() - 1;
int mij;
while(st <= dr) {
mij = (st + dr) / 2;
if(ad[node][mij].y == vec)
return mij;
else if(ad[node][mij].y < vec)
st = mij + 1;
else if(ad[node][mij].y > vec)
dr = mij - 1;
}
return -1;
};
int main() {
fin >> n;
source = 2 * n + 2; // aleg un nod sursa
destination = 2 * n + 1; // aleg un nod destinatie
for (int i = 1; i <= n; i++)
{
fin >> x >> y; // x pleaca; y intra
// adaug muchii de capacitate y de la sursa la primul set de noduri
ad[source].push_back({i, x, 0});
ad[i].push_back({source, 0, 0});
// adaug muchii de capacitate x de la al doilea set de noduri la destinatie
ad[i + n].push_back({destination, y, 0});
ad[destination].push_back({i + n, 0, 0});
}
// pun muchiile citite in problema cu capacitate 1
for (int i = 1; i <= n ; i++)
for(int j = n + 1; j <= 2 * n; j ++) {
if(i != j - n) {
ad[i].push_back({j, 1, 0});
ad[j].push_back({i, 0, 0});
}
}
// sortez listele de adiacenta crescator
for(int i = 1 ; i <= 2 * n + 2; i ++)
sort(ad[i].begin(), ad[i].end(), cmp);
// for(int i = 1; i <= 2 * n + 2; i ++) {
// cout << i << ": ";
// for(auto j : ad[i])
// cout << j.y << " ";
// cout << '\n';
// }
int max_flow = 0;
while(bfs()) {
for(auto vec : ad[destination]) {
int min_flow = INT_MAX;
int pos = findPosition(vec.y, destination);
if (explored[vec.y] == 0 || ad[vec.y][pos].flow == ad[vec.y][pos].capacity)
continue;
int node = destination;
father[destination] = vec.y;
while (father[node] != 0) {
int pos1 = findPosition(father[node], node);
min_flow = min(min_flow, ad[father[node]][pos1].capacity - ad[father[node]][pos1].flow);
node = father[node];
}
node = destination;
max_flow += min_flow;
while (father[node] != 0) {
int pos1 = findPosition(father[node], node);
ad[father[node]][pos1].flow += min_flow;
int pos2 = findPosition(node, father[node]);
ad[node][pos2].flow -= min_flow;
node = father[node];
}
}
}
fout << max_flow << '\n';
for(int i = 1; i <= n ; i ++)
for(auto j : ad[i]) {
if(j.flow == 1)
fout << i << " " << j.y - n << '\n';
}
return 0;
}