Pagini recente » Cod sursa (job #3129630) | Cod sursa (job #2851352) | Cod sursa (job #1613249) | Cod sursa (job #1589877) | Cod sursa (job #1444559)
#include<fstream>
#include<cstring>
#include<algorithm>
#include<vector>
#define pb push_back
using namespace std;
const int NM = 203;
const int INF = 0x3f3f3f3f;
vector<int> V[NM];
vector<int>::iterator it;
bool viz[NM];
int F[NM][NM];
int Q[NM],from[NM];
int ansX[NM],ansY[NM],K;
int N,Dest,maxflow;
void Update(){
int vf=Dest,mn=INF;
while(from[vf]!=-1)
{
mn=min(mn,F[from[vf]][vf]);
vf=from[vf];
}
vf=Dest;
if(mn==0 || mn==INF) return;
while(from[vf]!=-1)
{
F[from[vf]][vf]-=mn;
F[vf][from[vf]]+=mn;
vf=from[vf];
}
maxflow+=mn;
}
bool bfs(){
int i,nod;
bool ok=0;
memset(viz,0,sizeof(viz));
Q[0]=1; Q[1]=0;
viz[0]=1;
from[0]=-1;
for(i=1;i<=Q[0];++i)
{
nod=Q[i];
for(it=V[nod].begin();it!=V[nod].end();++it)
if(!viz[*it] && F[nod][*it]>0)
{
if(*it != Dest) Q[++Q[0]] = (*it);
viz[*it]=1;
from[*it]=nod;
}
if(viz[Dest]){ ok=1; Update(); viz[Dest]=0; }
}
return ok;
}
int main(){
ifstream cin("harta.in");
ofstream cout("harta.out");
int i,j,x,y;
cin>>N;
Dest=2*N+1;
for(i=1;i<=N;++i)
{
cin>>x>>y;
V[0].pb(i);
F[0][i]=x;
V[N+i].pb(Dest);
F[N+i][Dest]=y;
}
for(i=1;i<=N;++i)
for(j=1;j<=N;++j)
if(i!=j)
{
F[i][N+j]=1;
V[i].pb(N+j);
V[N+j].pb(i);
}
while(bfs()) ;
cout<<maxflow<<'\n';
for(i=1;i<=N;++i)
for(j=1;j<=N;++j)
if(F[j+N][i]) cout<<i<<' '<<j<<'\n';
return 0;
}