Pagini recente » Cod sursa (job #1644807) | Cod sursa (job #1936131) | Cod sursa (job #1606471) | Cod sursa (job #2616596) | Cod sursa (job #407638)
Cod sursa(job #407638)
#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];
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,-1,sizeof(prec));
Q.push(0);
viz[0]=1;
while(!Q.empty())
{
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);
}
}
return viz[N];
}
int min(int x,int y)
{
if(x<y)
return x;
return y;
}
void solve()
{
while(bfs())
{
for(int j=0;j<=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]);
F[j][N]+=Vmin;
F[N][j]-=Vmin;
for(int i=j;i!=0;i=prec[i])
{
F[prec[i]][i]+=Vmin;
F[i][prec[i]]-=Vmin;
}
cpl+=Vmin;
}
}
}
}
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;
}