Cod sursa(job #251536)

Utilizator ProtomanAndrei Purice Protoman Data 2 februarie 2009 21:37:42
Problema Critice Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.21 kb
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>

#define MAX 1024
#define pb push_back

using namespace std;

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

bool bfs(int source, int dest)
{
	queue <short> queBfs;
	queBfs.push(source);
	memset(vctTata, 0, sizeof(vctTata));
	vctTata[source] = -1;

	for (; !queBfs.empty(); )
		for (int i = 0, nod = queBfs.front(); i < lVecini[nod].size(); queBfs.pop(), i++)
			if (!vctTata[lVecini[nod][i]] && matCapac[nod][lVecini[nod][i]] > matFlux[nod][lVecini[nod][i]])
			{
				queBfs.push(lVecini[nod][i]);
				vctTata[lVecini[nod][i]] = nod;
			}

	return vctTata[dest] != 0;
}

void flux(int source, int dest)
{
	for (; bfs(source, dest); )
		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);

		matCapac[node1][node2] = matCapac[node2][node1] = capac + 1;
		if (bfs(1, nrNod))
			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;
}