Pagini recente » Cod sursa (job #2235182) | Cod sursa (job #3215729) | Cod sursa (job #2910957) | Cod sursa (job #407699) | Cod sursa (job #2469761)
#include <fstream>
#include <iostream>
#include <bitset>
#include <vector>
#include <deque>
#define DIM 210
using namespace std;
ifstream fin("fmcm.in");
ofstream fout("fmcm.out");
bitset<DIM> U;
vector<int> L[DIM];
int C[DIM][DIM],F[DIM][DIM],T[DIM];
deque<int> q;
pair <int,int> sol[100010];
int n,m,i,x,y,z,flux,cp,p,mn,j,d,cnt;
int bfs(){
int destinatie=0;
U.reset();
U[0]=1;
q.push_back(0);
while(!q.empty()){
int nod=q.front();
for(int i=0;i<L[nod].size();i++){
int vecin=L[nod][i];
if(U[vecin]==0 && C[nod][vecin]>F[nod][vecin]){
U[vecin]=1;
q.push_back(vecin);
T[vecin]=nod;
if(vecin==2*n+1)
destinatie=1;
}
}
q.pop_front();
}
return destinatie;
}
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(j-i != n){
L[i].push_back(j);
L[j].push_back(i);
C[i][j]=1;
}
}
d=2*n+1;
while(bfs()){
for(i=0;i<L[d].size();i++){
p=L[d][i];
if(C[p][d] > F[p][d] && U[p]==1 ){
mn=C[p][d]-F[p][d];
cp=p;
while(cp){
if(C[T[cp]][cp]-F[T[cp]][cp] < mn)
mn=C[T[cp]][cp]-F[T[cp]][cp];
cp=T[cp];
}
F[p][d] += mn;
F[d][p] -= mn;
cp=p;
while(cp){
F[T[cp]][cp]+=mn;
F[cp][T[cp]]-=mn;
cp=T[cp];
}
}
}
}
for(i=1;i<=n;i++)
for(j=n+1;j<=2*n;j++)
if(F[i][j]){
sol[++cnt].first=i;
sol[cnt].second=j-n;
}
fout<<cnt<<"\n";
for(i=1;i<=cnt;i++)
fout<<sol[i].first<<" "<<sol[i].second<<"\n";
return 0;
}