Pagini recente » Cod sursa (job #789494) | Istoria paginii runda/34554e/clasament | Cod sursa (job #1735298) | Cod sursa (job #1871881) | Cod sursa (job #475771)
Cod sursa(job #475771)
using namespace std;
#include<iostream>
#include<fstream>
#include<cstring>
#include<queue>
#define Nmax 105
#define pb push_back
#define oo 0x3f3f3f3f
ofstream fout("harta.out");
int in[Nmax],out[Nmax];
vector<int> G[2*Nmax+2];
int C[2*Nmax+2][2*Nmax+2],F[2*Nmax+2][2*Nmax+2],N,M,ante[2*Nmax+2];
int viz[2*Nmax+2];
int BFS()
{queue<int> q;
int u;
vector<int>::iterator it;
memset(viz,0,sizeof(viz));
q.push(0);
viz[0]=1;
while(!q.empty())
{
u=q.front();
q.pop();
for(it=G[u].begin();it!=G[u].end();it++)
{
if(viz[*it]==0)
if(F[u][*it]<C[u][*it])
{//cout<<0;
viz[*it]=1;
ante[*it]=u;
q.push(*it);
if(*it==2*N+1)
return 1;
}
}
}
return 0;
}
void solve()
{int i,j,flow,fmin;
for(i=1;i<=N;i++)
{C[0][i]=out[i];
G[0].pb(i);
G[i].pb(0);
for( j=1;j<=N;j++)
if(i!=j)
{ C[i][N+j]=1;
G[i].pb(N+j);
G[N+j].pb(i);
}
}
//cout<<0;
for(i=1;i<=N;i++)
{C[N+i][N+N+1]=in[i];
G[N+i].pb(N+N+1);
G[N+1+N].pb(N+i);
}
for(flow=0;BFS(); flow+=fmin)
{ //cout<<1;
fmin=oo;
for(i=2*N+1;i>0;i=ante[i])
{
fmin=min(fmin,C[ante[i]][i]-F[ante[i]][i]);
//cout<<i;
}
for(i=2*N+1;i>0;i=ante[i])
{
F[ante[i]][i]+=fmin;
F[i][ante[i]]-=fmin;
}
}
fout<<flow<<"\n";
for(i=1;i<=N;i++)
for(j=N+1;j<=2*N;j++)
if(F[i][j]==1)
fout<<i<<" "<<j-4<<"\n";
}
void cit()
{int x,y,i;
ifstream fin("harta.in");
fin>>N;
for(i=1;i<=N;i++)
{
fin>>x>>y;
in[i]=y;//<==e bine asa stay cool
out[i]=x;
}
fin.close();
}
int main()
{
cit();
solve();
fout.close();
return 0;
}