Pagini recente » Cod sursa (job #1407851) | Cod sursa (job #2666237) | Cod sursa (job #1013754) | Cod sursa (job #298790) | Cod sursa (job #3188039)
//ALEXANDRU MICLEA
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
//VARIABLES
int inf = 1e9 + 7;
int n, m;
int capacitate[205][205];
int flux[205][205];
int flux_pe_nod[205];
int tata[205];
int nod_terminal;
vector<int> gr[205];
queue<int> q;
//FUNCTIONS
int drum_ameliorare() {
for(int i = 0; i <= nod_terminal; i++){
tata[i] = -1;
}
tata[0] = -2;
flux_pe_nod[0] = inf;
while (!q.empty()) q.pop();
q.push(0);
while (!q.empty()) {
int nod_curent = q.front();
q.pop();
for (auto& nod_adiacent : gr[nod_curent]){
if (tata[nod_adiacent] == -1 && capacitate[nod_curent][nod_adiacent] - flux[nod_curent][nod_adiacent] > 0) {
tata[nod_adiacent] = nod_curent;
flux_pe_nod[nod_adiacent] = min(flux_pe_nod[nod_curent], capacitate[nod_curent][nod_adiacent] - flux[nod_curent][nod_adiacent]);
if (nod_adiacent == nod_terminal) return flux_pe_nod[nod_adiacent];
q.push(nod_adiacent);
}
}
}
return 0;
}
//MAIN
int main() {
//#define FILE_INPUT
#ifdef INFOARENA
ifstream fin("harta.in"); ofstream fout("harta.out");
cin.rdbuf(fin.rdbuf()); cout.rdbuf(fout.rdbuf());
#endif
#ifdef FILE_INPUT
ifstream fin("file.in"); cin.rdbuf(fin.rdbuf());
ofstream fout("file.out"); cout.rdbuf(fout.rdbuf());
#endif
cin >> n;
nod_terminal = 2 * n + 1;
for (int i = 1; i <= n; i++)
{
int x, y;
cin >> x >> y; // grad exterior -> grad interior
capacitate[0][i] += x;
capacitate[n + i][2*n + 1] += y;
gr[0].push_back(i);
gr[i].push_back(0);
gr[2*n + 1].push_back(n + i);
gr[n + i].push_back(2 * n + 1);
}
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
if (j == i) continue;
capacitate[i][n+j] = 1;
gr[i].push_back(n + j);
gr[n + j].push_back(i);
}
}
// aici urmeaza sa fac flux
int flux_total = 0;
int flux_nou;
while (flux_nou = drum_ameliorare()){
flux_total += flux_nou;
int nod_curent = nod_terminal;
while (nod_curent != 0) {
int nod_precedent = tata[nod_curent];
flux[nod_curent][nod_precedent] -= flux_nou;
flux[nod_precedent][nod_curent] += flux_nou;
nod_curent = nod_precedent;
}
}
vector <pair<int,int>> ans;
for (int i = 1; i <= n; i++) {
for (int j = n + 1; j <= 2 * n; j++) {
int ii = (i > n) ? i - n : i;
int jj = (j > n) ? j - n : j;
if (flux[i][j]) {
ans.push_back({ii,jj});
flux[i][j]--;
}
}
}
cout << ans.size() << '\n';
for (auto& x : ans) cout << x.first << ' ' << x.second << '\n';
return 0;
}