Cod sursa(job #81640)

Utilizator peanutzAndrei Homorodean peanutz Data 3 septembrie 2007 16:00:52
Problema Critice Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.29 kb
#include <stdio.h>
#include <memory.h>

#define NMAX 1002
#define MMAX 10002
#define INFI 0x3f3f3f3f

int cap[NMAX][NMAX];
int list[NMAX][NMAX];
int n, m;
int a[MMAX], b[MMAX];
int source, sink;

#define DIM 4000000
char buf[DIM];
int poz;
#define cin(x)		\
{			\
	x = 0;		\
	while(buf[poz] < '0' || buf[poz] > '9')  \
		if(++poz == DIM)		\
			fread(buf, 1, DIM, stdin), poz = 0; 	\
	while(buf[poz] >= '0' && buf[poz] <= '9')		\
	{							\
		x = x*10 + (buf[poz]-'0');			\
		if(++poz == DIM)				\
			fread(buf, 1, DIM, stdin), poz = 0;	\
	}							\
}								\

void read()
{
	fread(buf, 1, DIM, stdin);

	int i;
	int c;
	cin(n);
	cin(m);
	for(i = 1; i <= m; ++i)
	{
		cin(a[i]); 
		cin(b[i]);
		cin(c);
		cap[a[i]][b[i]] = c;
        	cap[b[i]][a[i]] = c;

		list[ a[i] ][ ++list[ a[i] ][0] ] = b[i];
		list[ b[i] ][ ++list[ b[i] ][0] ] = a[i];
	}
	source = 1, sink = n;
}

#define MIN(a, b) ((a) < (b)) ? (a) : (b)

int bf(short type)
{
	int i, x, y;
	int q[NMAX], t[NMAX];
	short uz[NMAX], ok = 1;
	int inc, sf;
	
	memset(uz, 0, sizeof(uz));

	inc = sf = 1;
	q[1] = source;
	++uz[source];

	while(inc <= sf && ok)
	{
		x = q[inc++];

		for(y = list[x][0]; y; --y)
		{
			i = list[x][y];

			if(cap[x][i] && !uz[i])
			{
				++uz[i];
				q[++sf] = i;
				t[i] = x;
				
				ok -= (i == sink);
			}
		}
	}
	if(!uz[sink])
		return 0;
    if(type)
        return 1;

	int min = INFI;
	for(i = sink; i != source; i = t[i])
		min = MIN(min, cap[ t[i] ][i]);

	for(i = sink; i != source; i = t[i])
		cap[ t[i] ][i] -= min, cap[i][ t[i] ] += min;

	return min;
}

int main()
{
	freopen("critice.in", "r", stdin);
	freopen("critice.out", "w", stdout);

	read();

	while(bf(0));
	
	printf("            \n");
    	int nr = 0;
	for(int i = 1, ok; i <= m; ++i)
	{
        	ok = 1;
		if(!cap[ a[i] ][ b[i] ])
		{
			++cap[ a[i] ][ b[i] ];
			if(bf(1))
				printf("%d\n", i), ++nr, ok = 0;
			--cap[ a[i] ][ b[i] ];
		}
		if(!cap[ b[i] ][ a[i] ] && ok)
        	{
			++cap[ b[i] ][ a[i] ];
			if(bf(1))
				printf("%d\n", i), ++nr;
			--cap[ b[i] ][ a[i] ];
        	}
	}
	fseek(stdout, 0, SEEK_SET);
	printf("%d", nr);

	return 0;
}