Cod sursa(job #3134617)

Utilizator Ilie_MityIlie Dumitru Ilie_Mity Data 29 mai 2023 20:46:27
Problema Taramul Nicaieri Scor 10
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.15 kb
//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;
}