Pagini recente » Cod sursa (job #2949718) | Cod sursa (job #2112003) | Cod sursa (job #2976961) | Cod sursa (job #3270030) | Cod sursa (job #447325)
Cod sursa(job #447325)
#include<stdio.h>
#include<stdlib.h>
#include<vector>
#define FIN "harta.in"
#define FOUT "harta.out"
#define NMAX 204
using namespace std;
int source,sink;
vector< int > G[NMAX];
int N,M,c,x,y,viz[NMAX],coada[NMAX],F[NMAX][NMAX],RT[NMAX],fmax,fmin,C[NMAX][NMAX],flux;
int BF()
{
memset(viz,0,sizeof(viz));
int p,q;
coada[p = q = 1] = source;
viz[source] = 1;
while( p <= q )
{
int nod = coada[p++];
vector< int >::iterator it;
for(it = G[nod].begin() ; it != G[nod].end() ; it++)
{
if( !C[nod][ *it ] || viz[ *it ]) continue;
viz [ *it ] = 1;
RT[ *it ]=nod;
coada[ ++q ] = *it;
if(*it==sink) {return 1;}
}
}
return 0;;
}
int main()
{
freopen(FIN,"r",stdin);
freopen(FOUT,"w",stdout);
scanf("%d\n",&N);
source=0;
sink=2*N+1;
for(int i = 1 ; i <= N ; i++)
{
scanf("%d %d",&x,&y);
C[source][i] = x;
C[i+N][sink] = y;
G[source].push_back(i);
G[i].push_back(0);
G[i+N].push_back(2*N+1);
G[sink].push_back(i+N);
}
for(int i=1;i<=N;i++)
for(int j=N+1;j<sink ; j++)
{ C[i][j]=1;
G[i].push_back(j);
G[j].push_back(i);
}
for(int i=1;i<=N;i++) C[i][i+N]=0;
for( ; BF() ; )
{
for( int nod = sink ;nod!=source ; nod=RT[nod])
{
C[RT[nod]][nod] -= 1;
C[nod][RT[nod]] += 1;
}
flux += 1;
}
printf("%d\n",flux);
for(int i=1;i<=N;i++)
for(int j=N+1;j<=2*N;j++)
if(!C[i][j] && j!=i+N ) printf("%d %d\n",i,j-N);
return 0;
}