Pagini recente » Cod sursa (job #1115259) | Cod sursa (job #2913491) | Cod sursa (job #1693034) | Cod sursa (job #2757110) | Cod sursa (job #2957629)
#include <iostream>
#include <bits/stdc++.h>
#include <fstream>
#define mx 10001
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
#define minim min(x,flux)
int n, iesire,intrare;
int rgraf[2 * mx][2 * mx];
bool bfs(int s, int t,int tata[], bool vizitat[]) {
queue<int> q;
vizitat[s] = true;
tata[s] = -1;
q.push(s);
while (!q.empty()) {
int front = q.front();
q.pop();
for (int i = 1; i <= t; ++i) {
if (vizitat[i] == false && rgraf[front][i] > 0) {
if (i == t) {
tata[i] = front;
return true;
}
vizitat[i] = true;
q.push(i);
tata[i] = front;
}
}
}
//daca se poate ajunge la destinatie
return vizitat[t];
}
int main() {
f >> n;
for(int i = 1;i<=n;i++)
{
f>>iesire>>intrare;
rgraf[0][i] = iesire;
rgraf[i+n][2*n+1] = intrare;
}
for(int i = 1;i<=n;i++)
for (int j = n+1; j <= 2*n; ++j) {
if(j-n != i)
rgraf[i][j] = 1;
}
int tata[2*n + 2];
for (int i = 0; i < 2*n + 2; i++)
tata[i] = -1;
bool vizitat[2*n + 2];
for (int i = 0; i <2*n + 2; i++)
vizitat[i] = false;
vector<int> veciniFinal;
for (int i = n + 1; i <= 2*n; i++)
veciniFinal.push_back(i);
int cuplaje = 0;
while (bfs(0, 2*n +1, tata, vizitat)) {
for (auto j: veciniFinal) {
if (rgraf[j][2*n + 1] > 0 && vizitat[j] == true) {
tata[2*n + 1] = j;
int flux = INT_MAX;
int u = 2*n + 1;
while (u != 0) {
int x = rgraf[tata[u]][u];
flux = minim;
u = tata[u];
}
if (flux != 0) {
cuplaje += 1;
u = 2*n + 1;
while (u != 0) {
int vecin = tata[u];
rgraf[vecin][u] -= flux;
rgraf[u][vecin] += flux;
u = tata[u];
}
}
}
}
for (int i = 0; i <= 2*n + 1; i++)
tata[i] = -1;
for (int i = 0; i <= 2*n + 1; i++)
vizitat[i] = false;
}
g << cuplaje << '\n';
for (int i = 1; i <= n; ++i) {
for (int j = n + 1; j <= 2*n; ++j) {
if (rgraf[i][j] == 0 && rgraf[j][i] != 0)
g << i << ' ' << j - n << '\n';
}
}
f.close();
f.close();
return 0;
}