Cod sursa(job #132066)

Utilizator plastikDan George Filimon plastik Data 4 februarie 2008 22:56:50
Problema Critice Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.41 kb
#include <cstdio>
#include <deque>
using namespace std;

const int MAX_N = 1024;
const int INF = 700000;
int C[MAX_N][MAX_N], IC[MAX_N][MAX_N], prev[MAX_N], M, N;
bool U[MAX_N], P[MAX_N][MAX_N];
deque<int> L[MAX_N];
deque<int> Q, S;
deque<pair<int, int> > E;

bool breadthFirst(int src, int snk) {
	if (src == snk)
		return true;
	
	int i, c, n;
	for (i = 1; i <= N; ++ i) {
		U[i] = false;
		prev[i] = -1;
	}
	U[src] = true;
	Q.clear();

	Q.push_back(src);
	while (Q.empty() == false) {
		c = Q.front();
		Q.pop_front();
		for (i = 0; i < L[c].size(); ++ i) {
			n = L[c][i];
			if (U[n] == false && C[c][n] > 0) {
				U[n] = true;
				prev[n] = c;
				Q.push_back(n);
				if (n == snk)
					return true;
			}
		}
	}
	return false;
}

int pathCapacity() {
	int dif = -1, c, src = 1, snk = N;
	for (c = snk; prev[c] != -1; c = prev[c])
		if (dif == -1 || C[prev[c]][c] < dif)
			dif = C[prev[c]][c];
	if (c != src || dif == -1)
		return 0;
	return dif;
}

int flowRoute() {
	int dif = breadthFirst(1, N), snk = N, c;
	if (dif == 0)
		return 0;
	for (c = snk; prev[c] != -1; c = prev[c]) {
		C[prev[c]][c] -= dif;
		C[c][prev[c]] += dif;
	}
	
	return dif;
}

inline int maxFlow() {
	int ans = 0, route = 0;
	while (route = flowRoute())
		ans += route;
	return ans;
}

int main() {
	freopen("critice.in", "r", stdin);
	freopen("critice.out", "w", stdout);
	
	scanf("%d %d", &N, &M);
	int i, v1, v2, c;
	for (i = 0; i < M; ++ i) {
		scanf("%d %d %d", &v1, &v2, &c);
		C[v1][v2] = C[v2][v1] = c;
		L[v1].push_back(v2);
		L[v2].push_back(v1);
		E.push_back(make_pair(v1, v2));		
		IC[v1][v2] = IC[v2][v1] = c;
	}

	maxFlow();
	
	for (i = 1; i <= N; ++ i)
		L[i].clear();
	
	int j;
	for (i = 1; i <= N; ++ i)
		for (j = 1; j <= N; ++ j)
			P[i][j] = false;
	for (i = 1; i <= N; ++ i)
		for (j = 1; j <= N; ++ j)
			if (P[i][j] == false && IC[i][j] - C[i][j] > 0) {
				P[i][j] = P[j][i] = true;
				C[j][i] = IC[i][j] - C[i][j];
				
				if (C[i][j] > 0)
					L[i].push_back(j);
				if (C[j][i] > 0)
					L[j].push_back(i);
			}

	int src = 1, snk = N, ns;	
	for (i = 0; i < M; ++ i) {
		v1 = E[i].first;
		v2 = E[i].second;
		if (C[v2][v1] == IC[v1][v2] && (breadthFirst(src, v1) && breadthFirst(v2, snk))) {
				S.push_back(i + 1);
				continue;
		}		
		if (C[v1][v2] == IC[v2][v1] && (breadthFirst(src, v2) && breadthFirst(v1, snk)))
				S.push_back(i + 1);
	}
	
	ns = S.size();
	printf("%d\n", ns);
	for (i = 0; i < ns; ++ i)
		printf("%d\n", S[i]);
	
	return 0;
}