Pagini recente » Cod sursa (job #215198) | Cod sursa (job #2616739) | Cod sursa (job #2345271) | Cod sursa (job #225153) | Cod sursa (job #2662204)
#include <fstream>
#include <vector>
#include <bitset>
#define K 204
using namespace std;
ifstream fin("harta.in");
ofstream fout("harta.out");
int n,i,j,x,y,f[K][K],c[K][K],q[K],t[K],tata,vecin,N,scad,flux;
bitset <K> viz;
vector <int> v[K];
int bfs(){
int p,u;
viz.reset();
q[1]=0; viz[0]=1;
for(p=u=1;p<=u;p++){
int nod=q[p];
for(int i=0;i<v[nod].size();i++){
int vecin=v[nod][i];
if(!viz[vecin] && c[nod][vecin]>f[nod][vecin]){
q[++u]=vecin;
viz[vecin]=1;
t[vecin]=nod;
if(vecin==N)
return 1;
}
}
}
return 0;
}
int main(){
fin>>n; N=2*n+1;
for(i=1;i<=n;i++){
fin>>x>>y;
v[0].push_back(i);
v[i].push_back(0);
c[0][i]=x;
v[n+i].push_back(N);
v[N].push_back(n+i);
c[n+i][N]=y;
}
for(i=1;i<=n;i++)
for(j=n+1;j<N;j++)
if(j-i!=n){
v[i].push_back(j);
v[j].push_back(i);
c[i][j]=1;
}
while(bfs()){
for(i=0;i<v[N].size();i++){
vecin=v[N][i];
if(viz[vecin] && c[vecin][N]>f[vecin][N]){
scad=c[vecin][N]-f[vecin][N];
for(x=vecin;t[x];x=t[x])
scad=min(scad,c[t[x]][x]-f[t[x]][x]);
f[vecin][N]+=scad;
f[N][vecin]-=scad;
flux+=scad;
for(x=vecin;t[x];x=t[x])
f[t[x]][x]+=scad,
f[x][t[x]]-=scad;
}
}
}
fout<<flux<<"\n";
for(i=1;i<=n;i++)
for(j=n+1;j<N;j++)
if(f[i][j]==1)
fout<<i<<" "<<j-n<<"\n";
return 0;
}