Cod sursa(job #252645)

Utilizator ProtomanAndrei Purice Protoman Data 4 februarie 2009 19:26:06
Problema Critice Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.44 kb
#include <stdio.h>
#include <algorithm>
#include <vector>

#define MAX 1024
#define pb push_back

using namespace std;

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

inline bool bfs(int source, int dest)
{
	short 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;

	return vctTata[dest] != 0;
}

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

inline void dfs(int nod, short ct)
{
	selNod[nod] |= ct;
	sel[nod] = 1;

	for (int i = 0; i < lVecini[nod].size(); i++)
		if (!sel[lVecini[nod][i]] && matCapac[nod][lVecini[nod][i]] > abs(matFlux[nod][lVecini[nod][i]]))
			dfs(lVecini[nod][i], ct);
}

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

	memset(sel, 0, sizeof(sel));
	dfs(1, 1);
	memset(sel, 0, sizeof(sel));
	dfs(nrNod, 2);

	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 ((selNod[node1] | selNod[node2]) == 3)
			vctSol.pb(i);
	}

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

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