Pagini recente » Cod sursa (job #2802809) | Cod sursa (job #2553836) | Cod sursa (job #2927067) | Cod sursa (job #1832388) | Cod sursa (job #2469794)
#include <fstream>
#include <vector>
#include <deque>
#define DIM 210
using namespace std;
ifstream fin ("harta.in");
ofstream fout("harta.out");
int n,i,j,f,x,y,nod,vecin,minim,C[DIM][DIM],F[DIM][DIM],T[DIM],ok[DIM];
vector< int > L[DIM];
deque< int > q;
int bfs(){
ok[0]=1;
for (i=1;i<=2*n+1;i++)
ok[i]=0;
q.push_back(0);
while (!q.empty()){
nod=q.front();
q.pop_front();
for (i=0;i<L[nod].size();i++){
vecin=L[nod][i];
if (!ok[vecin] && C[nod][vecin]>F[nod][vecin]){
ok[vecin]=1;
T[vecin]=nod;
q.push_back(vecin);
}
}
}
return ok[2*n+1];
}
int main(){
fin>>n;
for (i=1;i<=n;i++){
fin>>x>>y;
C[0][i]=x;
C[n+i][2*n+1]=y;
L[0].push_back(i);
L[i].push_back(0);
L[n+i].push_back(2*n+1);
L[2*n+1].push_back(n+i);
}
for (i=1;i<=n;i++)
for (j=n+1;j<=2*n;j++)
if (i+n!=j){
L[i].push_back(j);
L[j].push_back(i);
C[i][j]=1;
}
while (bfs())
for (i=0;i<L[2*n+1].size();i++){
nod=L[2*n+1][i];
if (ok[nod] && C[nod][2*n+1]>F[nod][2*n+1]){
minim=C[nod][2*n+1]-F[nod][2*n+1];
for (j=nod;j!=0;j=T[j])
minim=min(minim,C[T[j]][j]-F[T[j]][j]);
f+=minim;
F[nod][2*n+1]+=minim;
F[2*n+1][nod]-=minim;
for (j=nod;j!=0;j=T[j]){
F[T[j]][j]+=minim;
F[j][T[j]]-=minim;
}
}
}
fout<<f<<'\n';
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
if (F[i][n+j]==1)
fout<<i<<" "<<j<<'\n';
fin.close();
fout.close();
return 0;
}