Pagini recente » Cod sursa (job #3340032) | Cod sursa (job #564284) | Cod sursa (job #2238154) | Cod sursa (job #3336807) | Cod sursa (job #3323808)
#include <fstream>
#include <vector>
#include <bitset>
#include <queue>
using namespace std;
const int NMAX = 202;
ifstream cin("harta.in");
ofstream cout("harta.out");
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;
}
bitset <NMAX + 2> viz;
pair <int, int> tata[NMAX + 2];
bool bfs() {
viz = 0;
for(int i = 1; i <= dest; i++) {
tata[i].first = 0;
tata[i].second = -1;
}
queue <int> q;
viz[sursa] = 1;
q.push(sursa);
while(!q.empty()) {
int now = q.front();
q.pop();
for(int i = 0; i < v[now].size(); i++) {
muchie x = v[now][i];
if(!viz[x.nod] && x.flux < x.cap) {
viz[x.nod] = 1;
q.push(x.nod);
tata[x.nod].first = now;
tata[x.nod].second = i;
}
}
}
return viz[dest];
}
int recons(int nod, int minn) {
while(tata[nod].first) {
minn = min(minn, v[tata[nod].first][tata[nod].second].cap - v[tata[nod].first][tata[nod].second].flux);
if(minn <= 0)
return minn;
nod = tata[nod].first;
}
return minn;
}
void change(int a, int b, int id, int val) {
v[a][id].flux += val;
v[b][v[a][id].pereche].flux -= val;
}
void update(int nod, int add) {
while(tata[nod].first) {
change(tata[nod].first, nod, tata[nod].second, add);
nod = tata[nod].first;
}
}
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); ///1)
addedge(n + i, dest, iese); ///3)
for(int j = 1; j <= n; j++) { ///2)
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 - n});
}
}
}
cout << ans.size() << '\n';
for(auto x : ans)
cout << x.first << " " << x.second << '\n';
return 0;
}