Pagini recente » Cod sursa (job #2570346) | Cod sursa (job #2092398) | Cod sursa (job #2821062) | Cod sursa (job #1739679) | Cod sursa (job #1235573)
#include <fstream>
#include <bitset>
#include <queue>
#include <list>
#define DIM 310
using namespace std;
ifstream f("harta.in");
ofstream g("harta.out");
int n,z,k;
int T[DIM];
int C[DIM][DIM],F[DIM][DIM];
list<int> L[DIM];
list<int>::iterator it;
queue<int> q;
bitset<DIM> viz;
inline int bfs(){
int nod;
viz.reset();
for(register int i=1;i<=z;i++)
T[i]=-1;
q.push(0),viz[0]=1;
while(!q.empty()){
nod=q.front(),q.pop();
for(it=L[nod].begin();it!=L[nod].end();it++){
if(!viz[*it] && C[nod][*it]>F[nod][*it])
T[*it]=nod,viz[*it]=1,q.push(*it);
}
}
return viz[z];
}
int main(void){
register int i,j,x,y,minim;
f>>n,z=2*n+1;
for(i=1;i<=n;i++){
f>>x>>y;
L[0].push_back(i),L[i].push_back(0);
L[i+n].push_back(z),L[z].push_back(i+n);
C[0][i]=x,C[i+n][z]=y;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j)
C[i][j+n]=1,L[i].push_back(j+n),L[j+n].push_back(i);
T[0]=-1;
while(bfs()){
for(it=L[z].begin();it!=L[z].end();it++){
if(viz[*it] && C[*it][z]>F[*it][z]){
x=*it;
minim=C[*it][z]-F[*it][z];
while(T[x]>=0) minim=min(C[T[x]][x]-F[T[x]][x],minim),x=T[x];
x=*it;
F[x][z]+=minim,F[z][x]-=minim;
while(T[x]>=0) F[T[x]][x]+=minim,F[x][T[x]]-=minim,x=T[x];
k+=minim;
}
}
}
g<<k<<"\n";
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(i!=j && F[i][j+n])
g<<i<<" "<<j<<"\n";
f.close();
g.close();
return 0;
}