Pagini recente » Cod sursa (job #1358645) | Cod sursa (job #409769) | Cod sursa (job #1997718) | Cod sursa (job #2052842) | Cod sursa (job #3187589)
//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 tata[205];
int luat[205];
vector<int> gr[105];
vector<pair<int,int>> voluntar;
queue<int> q;
//FUNCTIONS
int drum_ameliorare() {
//cout << "in\n";
for (auto& x : tata) x = -1;
tata[0] = -2;
q.push(0);
int ok = 0;
while (!q.empty()){
int nod = q.front();
//cout << nod << ' ';
q.pop();
if (nod == 2*n+1) {
ok = 1;
continue;
}
for (auto& x : gr[nod]) {
if (tata[x] == -1 && capacitate[nod][x] - flux[nod][x] > 0){
tata[x] = nod;
q.push(x);
}
}
}
//cout << "\nout\n";
return ok;
}
//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());
#endif
cin >> n;
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[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);
// TODO see if this is correct
}
}
while (drum_ameliorare()) {
for (auto& x : gr[2*n+1]){
if (!tata[x]) continue;
tata[2*n + 1] = x;
//cout << "in while\n";
int nod_curent = 2*n + 1;
int flux_minim = inf;
while (nod_curent != 0) {
//cout << nod_curent << ' ' << tata[nod_curent] << '\n';
flux_minim = min(flux_minim, capacitate[tata[nod_curent]][nod_curent] - flux[tata[nod_curent]][nod_curent]);
nod_curent = tata[nod_curent];
}
nod_curent = 2 * n + 1;
while (nod_curent != 0) {
flux[tata[nod_curent]][nod_curent] += flux_minim;
flux[nod_curent][tata[nod_curent]] -= flux_minim;
nod_curent = tata[nod_curent];
}
}
}
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;
}