Pagini recente » Cod sursa (job #2585297) | Cod sursa (job #1612335) | Cod sursa (job #1697762) | Cod sursa (job #957821) | Cod sursa (job #2216878)
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
int n, s, t, pr[210], c[210][210];
pair <int, int> a[110];
vector <int> v[210];
vector <pair <int,int> > sol;
bool viz[210];
queue <int> Q;
bool bfs(){
for (int i=0; i<=t; i++) viz[i] = 0;
Q.push(s);
viz[s] = 1;
while (!Q.empty()){
int nod = Q.front();
Q.pop();
if (nod == t) continue;
for (auto it: v[nod]){
if (viz[it] || !c[nod][it]) continue;
pr[it] = nod;
viz[it] = 1;
Q.push(it);
}
}
return viz[t];
}
int main(){
ifstream cin ("harta.in");
ofstream cout ("harta.out");
cin >> n;
for (int i=1; i<=n; i++) cin >> a[i].fi >> a[i].se;
s = 0; t = 2*n + 1;
for (int i=1; i<=n; i++){
v[s].push_back(i);
v[i].push_back(s);
v[n+i].push_back(t);
v[t].push_back(n+i);
c[s][i] += a[i].fi;
c[n+i][t] += a[i].se;
for (int j=1; j<=n; j++){
if (i == j) continue;
v[i].push_back(j+n);
v[j+n].push_back(i);
c[i][j+n]++;
}
}
while (bfs()){
for (auto it: v[t]){
if (!viz[it] || !c[it][t]) continue;
pr[t] = it;
bool flag = 1;
for (int nod = t; nod != s && flag; nod = pr[nod])
if (!c[pr[nod]][nod]) flag = 0;
for (int nod = t; nod != s && flag; nod = pr[nod]){
c[pr[nod]][nod]--;
c[nod][pr[nod]]++;
}
}
}
for (int i=1; i<=n; i++){
for (auto it: v[i]){
if (it != s && !c[i][it]) sol.push_back({i, it-n});
}
}
cout << sol.size() << "\n";
for (auto it: sol) cout << it.fi << " " << it.se << "\n";
return 0;
}