Pagini recente » Cod sursa (job #2313527) | Cod sursa (job #1591961) | Cod sursa (job #1849935) | Cod sursa (job #741771) | Cod sursa (job #387377)
Cod sursa(job #387377)
using namespace std;
#include <cstdio>
int a[205][205],t[205],n,fm;
void write(){
freopen("harta.out","w",stdout);
printf("%d\n",fm);
for(int i=1;i<=n;++i)
for(int j=n+1;j<=2*n;++j)
if(a[i][j]==0 && i+n!=j)
printf("%d %d\n",i,j-n);
}
void citire(){
freopen("harta.in","r",stdin);
scanf("%d",&n);
for(int i=1 ; i<=n ; ++i)
for(int j=1 ; j<=n ; ++j)
if(i!=j)
a[i][n+j]=1;
int ies , intra;
for(int i=1 ; i<=n ; ++i){
scanf("%d%d",&ies, &intra);
a[0][i]=ies;
a[n+i][2*n+1]=intra;
}
}
int bfs(int s,int d){
int c[205], st=1,dr=1;
c[1]=s;
for(int i=0; i<=2*n+1 ; ++i)
t[i]=-2;
t[s]=-1;
while(st<=dr){
int k=c[st++];
for(int i=0;i<=2*n+1;++i)
if(t[i]==-2 && a[k][i]>0){
c[++dr]=i, t[i]=k;
if(i==d)
return 1;
}
}
return 0;
}
void ek(){
while(bfs(0,2*n+1)){
int cmin=200;
for(int i=2*n+1; t[i]!=-1; i=t[i])
if(cmin > a[t[i]][i])
cmin = a[t[i]][i];
fm += cmin;
for(int i=2*n+1; t[i]!=-1; i=t[i])
a[t[i]][i] -= cmin, a[i][t[i]] += cmin;
}
}
int main(){
citire();
ek();
write();
return 0;
}