Pagini recente » Cod sursa (job #1027573) | Cod sursa (job #948839) | Cod sursa (job #564290) | Cod sursa (job #3032041) | Cod sursa (job #3323728)
#include <iostream>
#include <vector>
using namespace std;
const int NMAX = 202;
struct muchie {
int nod;
int cap;
int flux;
int pereche;
};
vector <vector <muchie>> v;
int sursa, dest;
void addedge(int a, int b, int cap) {
v[a].push_back({b, cap, 0, -1});
v[b].push_back({a, 0, 0, -1});
v[a].back().pereche = v[b].size() - 1;
v[b].back().pereche = v[a].size() - 1;
}
vector <pair <int, int>> ans;
int main() {
int n;
cin >> n;
sursa = 2 * n + 1, dest = 2 * n + 2;
v.resize(dest + 1);
for(int i = 1; i <= n; i++) {
int intra, iese;
cin >> intra >> iese;
addedge(sursa, i, intra);
addedge(n + i, dest, iese);
for(int j = 1; j <= n; j++) {
if(i != j)
addedge(i, n + j, 1);
}
}
while(bfs()) {
for(int i = 0; i < v[dest].size(); i++) {
muchie x = v[dest][i];
if(viz[x.nod] && v[x.nod][x.pereche].flux < v[x.nod][x.pereche].cap) {
int add = recons(x.nod, v[x.nod][x.pereche].cap - v[x.nod][x.pereche].flux);
if(add > 0) {
change(x.nod, dest, x.pereche, add);
update(x.nod, add);
}
}
}
}
for(int i = 1; i <= n; i++) {
for(auto x : v[i]) {
if(x.flux == 1) {
ans.push_back({i, x.nod});
}
}
}
cout << ans.size() << '\n';
for(auto x : ans)
cout << x.first << " " << x.second << '\n';
return 0;
}