Cod sursa(job #251549)

Utilizator ProtomanAndrei Purice Protoman Data 2 februarie 2009 22:08:28
Problema Critice Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.38 kb
#include <stdio.h>
#include <algorithm>
#include <vector>

#define MAX 1024
#define pb push_back

using namespace std;

int nrNod, nrVert;
vector <int> vctSol, lVecini[MAX];
int vctTata[MAX];
short matCapac[MAX][MAX], matFlux[MAX][MAX];

inline bool bfs(int source, int dest, int ver)
{
	int queBfs[MAX];
	memset(vctTata, 0, sizeof(vctTata));
	vctTata[queBfs[0] = source] = -1;

	for (int queF = 0, queL = 0; queF <= queL; queF++)
		for (int i = 0, nod = queBfs[queF]; i < lVecini[nod].size(); i++)
			if (!vctTata[lVecini[nod][i]] && matCapac[nod][lVecini[nod][i]] > matFlux[nod][lVecini[nod][i]])
			{
				vctTata[queBfs[++queL] = lVecini[nod][i]] = nod;

				if (lVecini[nod][i] == dest && ver)
					return 1;
			}

	return vctTata[dest] != 0;
}

inline void flux(int source, int dest)
{
	for (; bfs(source, dest, 0); )
		for (int nod = 1; nod <= nrNod; nod++)
		{
			if (vctTata[nod] <= 0 || matCapac[nod][dest] - matFlux[nod][dest] <= 0)
				continue;
			int r = matCapac[nod][dest] - matFlux[nod][dest];

			for (int i = nod; i != source; i = vctTata[i])
				r = min(r, matCapac[vctTata[i]][i] - matFlux[vctTata[i]][i]);

			matFlux[nod][dest] += r;
			matFlux[dest][nod] -= r;
			for (int i = nod; i != source; i = vctTata[i])
			{
				matFlux[vctTata[i]][i] += r;
				matFlux[i][vctTata[i]] -= r;
			}
		}
}


int main()
{
	freopen("critice.in", "r", stdin);
	freopen("critice.out", "w", stdout);
	
	scanf("%d %d", &nrNod, &nrVert);

	for (int i = 1; i <= nrVert; i++)
	{
		int node1, node2, capac;
		scanf("%d %d %d", &node1, &node2, &capac);

		matCapac[node1][node2] = matCapac[node2][node1] = capac;
		lVecini[node1].pb(node2);
		lVecini[node2].pb(node1);
	}

	flux(1, nrNod);

	fclose(stdin);
	freopen("critice.in", "r", stdin);

	scanf("%d %d", &nrNod, &nrVert);

	for (int i = 1; i <= nrVert; i++)
	{
		int node1, node2, capac;
		scanf("%d %d %d", &node1, &node2, &capac);

		if (!(matCapac[node1][node2] == matFlux[node1][node2] ||
			matCapac[node2][node1] == matFlux[node2][node1]))
			continue;

		matCapac[node1][node2] = matCapac[node2][node1] = capac + 1;
		if (bfs(1, nrNod, 1))
			vctSol.pb(i);
		matCapac[node1][node2] = matCapac[node2][node1] = capac;
	}

	printf("%d\n", vctSol.size());
	for (int i = 0; i < vctSol.size(); i++)
		printf("%d\n", vctSol[i]);

	fclose(stdin);
	fclose(stdout);
	return 0;
}