Cod sursa(job #159343)

Utilizator city_guy91alex isip city_guy91 Data 14 martie 2008 08:20:33
Problema Critice Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.33 kb
#include <iostream>
#include <fstream>
#include <cstring>
#include <vector>

using namespace std;

int N, M;
int c[1001][1001],
	flow[1001][1001];
int pred[1001],
	q[1003];
bool col[1001];
vector<int> G[1001];

#define MIN(a, b) ((a < b) ? (a) : (b))

bool bfs() {
	memset(col, 0, sizeof(col));

	int head, tail;
	head = tail = 0;
	q[tail++] = 1;
	col[1] = true;

	while (head != tail) {
		int u = q[head++];

		for (vector<int>::iterator v = G[u].begin(); v != G[u].end(); ++v)
			if (!col[*v] && (c[u][*v] - flow[u][*v] > 0)) {
				q[tail++] = *v;
				col[*v] = true;
				pred[*v] = u;
			}
	}

	return col[N];
}

void search_and_mark(int u, bool *f) {
	f[u] = true;
	col[u] = true;

	for (vector<int>::iterator v = G[u].begin(); v != G[u].end(); ++v)
		if (c[u][*v] && !col[*v] && (c[u][*v] - flow[u][*v] != 0) && (c[u][*v] + flow[u][*v] != 0))
			search_and_mark(*v, f);
}

int main(int argc, char *argv[]) {
	FILE *fi = fopen("critice.in", "r");
	fscanf(fi, "%d %d", &N, &M);
	int u[10000], v[10000], w;
	for (int i(0); i < M; ++i) {
		fscanf(fi, "%d %d %d", &u[i], &v[i], &w);
		c[u[i]][v[i]] = c[v[i]][u[i]] = w;
		G[u[i]].push_back(v[i]);
		G[v[i]].push_back(u[i]);
	}
	fclose(fi);

	while (bfs()) {
		int increment = 1<<30;
		for (int u = N; pred[u] >= 1; u = pred[u])
			increment = MIN(increment, c[pred[u]][u] - flow[pred[u]][u]);
		for (int u = N; pred[u] >= 1; u = pred[u]) {
			flow[pred[u]][u] += increment;
			flow[u][pred[u]] -= increment;
		}
	}

	/*for (int i(1); i <= N; ++i) {
		for (int j(1); j <= N; ++j)
			cout << c[i][j] << " ";
		cout << endl;
	}*/

	/*for (int i(1); i <= N; ++i)
		for (int j(1); j <= N; ++j)
			if (flow[i][j])
				cout << i << " - " << j << ": " << c[i][j] << "/" << flow[i][j] << endl;*/

	memset(col, 0, sizeof(col));
	bool l[1001];
	memset(l, 0, sizeof(l));
	search_and_mark(1, l);
	/*for (int i(1); i <= N; ++i)
		cout << l[i] << " ";
	cout << endl;*/

	memset(col, 0, sizeof(col));
	bool r[1001];
	memset(r, 0, sizeof(r));
	search_and_mark(N, r);
	/*for (int i(1); i <= N; ++i)
		cout << r[i] << " ";
	cout << endl;*/

	int count(0);
	for (int i(0); i < M; ++i)
		if ((l[u[i]] && r[v[i]]) || (l[v[i]] && r[u[i]]))
			++count;

	FILE *fo = fopen("critice.out", "w");
	fprintf(fo, "%d\n", count);
	for (int i(0); i < M; ++i)
		if ((l[u[i]] && r[v[i]]) || (l[v[i]] && r[u[i]]))
			fprintf(fo, "%d\n", i + 1);
	fclose(fo);

	return 0;
}