Pagini recente » Cod sursa (job #3240681) | Cod sursa (job #1913783) | Cod sursa (job #1095475) | Cod sursa (job #850326) | Cod sursa (job #2447001)
#include <bits/stdc++.h>
using namespace std;
int n, i, j, k, maxflow, cap;
int past[208], flow[208][208], cnt[208];
queue<int> q;
void read();
void solve();
void write();
bool bfs();
int dfs(int node, int val);
int main()
{
read();
solve();
write();
return 0;
}
void read(){
freopen("harta.in", "r", stdin);
scanf("%d", &n);
for(i=1; i<=n; ++i){
int in, out;
scanf("%d%d", &in, &out);
flow[0][i]=out;
flow[i+n][2*n+1]=in;
k=k+in+out;
cap=cap+out;
}
k/=2;
return;
}
void solve(){
for(i=1; i<=n; ++i)
for(j=1; j<=n; ++j) if(i!=j)flow[i][j+n]=1;
while(bfs());
return;
}
void write(){
freopen("harta.out", "w", stdout);
printf("%d\n", k);
for(i=1; i<=n; ++i)
for(j=1; j<=n; ++j) if(i!=j && i!=0 && j!=2*n+1 && !flow[i][j+n]) printf("%d %d\n", j, i);
}
bool bfs(){
q.push(0);
for(i=0; i<=2*n+1; ++i) past[i]=cnt[i]=0;
cnt[0]=1;
while(!q.empty()){
int init=q.front(); q.pop();
for(int next=0; next<=2*n+1; ++next) if(flow[init][next]){
if(!cnt[next]){
cnt[next]=cnt[init]+1;
past[next]=init;
q.push(next);
}
}
}
if(!cnt[2*n+1]) return false;
int elim=1, pos=2*n+1;
while(pos){
flow[past[pos]][pos]-=elim;
flow[pos][past[pos]]+=elim;
pos=past[pos];
}
return true;
}