Pagini recente » Cod sursa (job #2081040) | Cod sursa (job #1763957) | Cod sursa (job #1753791) | Cod sursa (job #1694043) | Cod sursa (job #407624)
Cod sursa(job #407624)
#include<stdio.h>
#include<vector>
#include<queue>
#include<string.h>
#define Nmx 202
#define INF 10000001
using namespace std;
int n,gri[Nmx],viz[Nmx],gre[Nmx],prec[Nmx];
int C[Nmx][Nmx],F[Nmx][Nmx],cpl,N;
vector <int> G[Nmx];
queue <int> Q;
void citire()
{
scanf("%d",&n);
N=n+n+1;
for(int i=1;i<=n;++i)
{
scanf("%d%d",&gre[i],&gri[i]);
C[0][i]=gre[i];
C[i+n][N]=gri[i];
C[N][i+n]=-gri[i];
G[0].push_back(i);
G[i+n].push_back(N);
for(int j=1;j<=n;++j)
if(i!=j)
{
G[i].push_back(j+n);
C[i][j+n]=1;
}
}
}
int bfs()
{
vector <int> :: iterator it;
memset(viz,0,sizeof(viz));
memset(prec,0,sizeof(prec));
Q.push(0);
viz[0]=1;
while(!Q.empty())
if(Q.front()!=N)
{
int nod=Q.front();
Q.pop();
for(it=G[nod].begin();it!=G[nod].end();++it)
if(C[nod][*it]-F[nod][*it]>0&&!viz[*it])
{
viz[*it]=1;
prec[*it]=nod;
Q.push(*it);
}
}
else Q.pop();
return viz[N];
}
int min(int x,int y)
{
if(x<y)
return x;
return y;
}
void solve()
{
while(bfs())
{
for(int j=n+1;j<=n+n;++j)
{
if(C[j][N]-F[j][N]>0&&viz[j])
{
int Vmin=C[j][N]-F[j][n];
for(int i=j;i!=0;i=prec[i])
Vmin=min(Vmin,C[prec[i]][i]-F[prec[i]][i]);
if(Vmin)
{
for(int i=j;i!=0;i=prec[i])
{
F[prec[i]][i]+=Vmin;
F[i][prec[i]]-=Vmin;
}
++cpl;
}
}
}
}
}
void afis()
{
printf("%d\n",cpl);
for(int i=1;i<=n;++i)
for(int j=n+1;j<=n+n;++j)
if(F[i][j]&&i!=j-n)
printf("%d %d\n",i,j-n);
}
int main()
{
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
citire();
solve();
afis();
return 0;
}