Pagini recente » Cod sursa (job #1456114) | Cod sursa (job #2973396) | Cod sursa (job #1399065) | Cod sursa (job #410611) | Cod sursa (job #1789410)
# include <fstream>
# include <vector>
# include <deque>
# include <cstring>
# define DIM 210
# define INF 1000000000
# define pb push_back
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
vector <int> Lista[DIM];
deque <int> d;
int c[DIM][DIM],f[DIM][DIM],sol[2][DIM],Marcat[DIM],t[DIM];
int n,i,j,k,x,y,dm,mn;
int bfs(){
int ok=0;
memset(Marcat,0,sizeof(Marcat));
Marcat[0]=1;
d.pb(0);
while(!d.empty()){
int nc=d.front();
if(nc==2*n+1)
ok=1;
d.pop_front();
for(int i=0;i<Lista[nc].size();i++){
int nv=Lista[nc][i];
if(Marcat[nv]==0&&f[nc][nv]<c[nc][nv]){
d.pb(nv);
Marcat[nv]=1;
t[nv]=nc;
}
}
}
return ok;
}
int main () {
fin>>n;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++){
if(j==i)
continue;
Lista[i].pb(j+n);
Lista[j+n].pb(i);
c[i][j+n]=1;
}
for(i=1;i<=n;i++){
fin>>x>>y;
Lista[0].pb(i);
Lista[i].pb(0);
Lista[i+n].pb(2*n+1);
Lista[2*n+1].pb(i+n);
c[0][i]=x;
c[i+n][2*n+1]=y;
}
dm=2*n+1;
t[0]=-1;
while(bfs()){
for(j=0;j<Lista[dm].size();j++){
int nc=Lista[dm][j];
if(Marcat[nc]&&c[nc][dm]>f[nc][dm]){
mn=c[nc][dm]-f[nc][dm];
for(i=nc;t[i]!=-1;i=t[i])
mn=min(mn,c[t[i]][i]-f[t[i]][i]);
f[nc][dm]+=mn;
f[dm][nc]-=mn;
for(i=nc;t[i]!=-1;i=t[i]){
f[t[i]][i]+=mn;
f[i][t[i]]-=mn;
}
}
}
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(f[i][j+n]){
sol[0][++k]=i;
sol[1][k]=j;
}
fout<<k<<"\n";
for(i=1;i<=k;i++)
fout<<sol[0][i]<<" "<<sol[1][i]<<"\n";
return 0;
}