Pagini recente » Cod sursa (job #2541630) | Cod sursa (job #305992) | Cod sursa (job #3282508) | Cod sursa (job #1154984) | Cod sursa (job #3134617)
//Ilie Dumitru
#include<cstdio>
const int NMAX=105;
/*
Ideea de baza:
cuplaj maxim in graf bipartit, indegree este fluxul maxim pe output si outdegree este fluxul maxim pe input
S+-2> XXX -1-+>T
|-0> XXX -2-|
|-2> XXX -1-|
+-1> XXX -1-+
*/
int N;
int cnt[2][NMAX];
bool conect[NMAX][NMAX];
void solve()
{
int i, j, k;
for(i=0;i<N;++i)
{
for(j=0;j<N && cnt[0][i];++j)
if(i!=j && cnt[1][j])
{
conect[i][j]=1;
--cnt[1][j];
--cnt[0][i];
}
}
for(i=0;i<N;++i)
for(j=0;j<N && cnt[0][i];++j)
for(k=0;k<N && cnt[0][i] && !conect[i][j];++k)
if(conect[k][j] && !conect[k][i])
{
conect[k][j]=0;
conect[k][i]=1;
conect[i][j]=1;
--cnt[0][i];
--cnt[1][i];
}
}
int main()
{
FILE* f=fopen("harta.in", "r"), *g=fopen("harta.out", "w");
//FILE* f=stdin, *g=stdout;
int i, j, aux=0;
fscanf(f, "%d", &N);
for(i=0;i<N;++i)
fscanf(f, "%d%d", cnt[0]+i, cnt[1]+i), aux+=cnt[0][i];
solve();
fprintf(g, "%d\n", aux);
for(i=0;i<N;++i)
for(j=0;j<N;++j)
if(conect[i][j])
fprintf(g, "%d %d\n", i+1, j+1);
fclose(f);
fclose(g);
return 0;
}