Cod sursa(job #251546)

Utilizator ProtomanAndrei Purice Protoman Data 2 februarie 2009 21:59:04
Problema Critice Scor 70
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 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];

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

	for (; !queBfs.empty(); queBfs.pop())
		for (int i = 0, nod = queBfs.front(); i < lVecini[nod].size(); 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;

				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);

		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;
}