Pagini recente » Cod sursa (job #350607) | Cod sursa (job #213588) | Cod sursa (job #1831778) | Cod sursa (job #244719) | Cod sursa (job #324269)
Cod sursa(job #324269)
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
#define MAX_N 256
#define Inf 0x3f3f3f3f
int N, S, D;
queue<int> Q;
int c[MAX_N][MAX_N];
bool viz[MAX_N];
int tata[MAX_N];
inline bool BFS()
{
int x,y;
int i;
for(;!Q.empty();Q.pop());
Q.push(S);
memset(viz,0,sizeof(viz));
viz[S] = 1;
for(;!Q.empty();Q.pop())
{
x = Q.front();
for(y=1;y<=2*N+2;++y)
if(!viz[y] && c[x][y])
{
tata[y] = x;
Q.push(y);
viz[y] = 1;
}
}
if(viz[D])
{
int flx = Inf;
for(i = D; i!=S; i = tata[i])
flx = min(flx, c[tata[i]][i]);
for(i = D; i!=S; i = tata[i])
{
c[tata[i]][i] -= flx;
c[i][tata[i]] += flx;
}
return 1;
}
return 0;
}
int main()
{
freopen("harta.in","r",stdin);
freopen("harta.out","w",stdout);
scanf("%d",&N);
int i,j,x,y;
int sol = 0;
S = 2*N + 1; D = 2*N + 2;
for(i=1;i<=N;++i)
{
scanf("%d%d",&x,&y);
sol += x;
c[S][i] = c[i][S] = x;
c[i+N][D] = c[D][i+N] = y;
}
for(i=1;i<=N;++i)
for(j=1;j<=N;++j)
if(i!=j) c[i][j+N] = 1;
for(;BFS(););
printf("%d\n",sol);
for(i=1;i<=N;++i)
for(j=1;j<=N;++j)
if(i!=j && !c[i][j+N])
printf("%d %d\n",i,j);
return 0;
}