sgu402.cpp

SGU题库第四版前10题的题目解答。前三题是CPP程序

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

const int maxn = 10000;
const int maxm = 100000;
const int inf = 0x7fffffff;

struct Record {
	int fr, to, cap;
	
	void Input() {
		scanf("%d %d %d", &fr, &to, &cap);
		fr--;
		to--;
	}
};

struct Edge {
	int data, flow, cap, oppo;
	
	Edge() {
	}
	
	Edge(int data, int flow, int cap, int oppo) : data(data), flow(flow), cap(cap), oppo(oppo) {
	}
};

Record edge[maxm];
vector<Edge> link[maxn];
int queue[maxn], prev[maxn], path[maxn], add[maxn];
int n, m, ans;

void Add_Link(int a, int b, int c) {
	link[a].push_back(Edge(b, 0, c, link[b].size()));
	link[b].push_back(Edge(a, 0, 0, link[a].size() - 1));
}

void Init() {
	int i;
	for (i = 0; i < m; i++)
		edge[i].Input();
}

int Max_Flow(int captured, int source, int target, bool output) {
	int curr, succ, i, j, k, head, tail, res = 0;
	for (i = 0; i < n; i++)
		link[i].clear();
	for (i = 0; i < m; i++) {
		Add_Link(edge[i].fr, edge[i].to, edge[i].cap);
		Add_Link(edge[i].to, edge[i].fr, edge[i].cap);
	}
	bool flag = 1;
	while (flag) {
		flag = 0;
		for (i = 0; i < n; i++)
			prev[i] = -1;
		queue[0] = source;
		add[source] = inf;
		prev[source] = -2;
		for (head = tail = 0; !flag && head <= tail; head++) {
			curr = queue[head];
			for (i = link[curr].size() - 1; i >= 0; i--)
				if (link[curr][i].flow < link[curr][i].cap) {
					succ = link[curr][i].data;
					if (prev[succ] != -1 || succ == captured) continue;
					queue[++tail] = succ;
					add[succ] = min(add[curr], link[curr][i].cap - link[curr][i].flow);
					prev[succ] = curr;
					path[succ] = i;
					if (succ == target) {
						flag = 1;
						res += add[succ];
						for (j = succ; prev[j] >= 0; j = prev[j]) {
							link[prev[j]][path[j]].flow += add[succ];
							link[j][link[prev[j]][path[j]].oppo].flow -= add[succ];
						}
						break;
					}
				}
		}
	}
	if (output) {
		int sum = 0;
		for (i = 0; i < m; i++)
			if (edge[i].fr != captured && edge[i].to != captured && (prev[edge[i].fr] == -1) != (prev[edge[i].to] == -1)) sum++;
		printf("%d\n", sum);
		for (i = 0; i < m; i++)
			if (edge[i].fr != captured && edge[i].to != captured && (prev[edge[i].fr] == -1) != (prev[edge[i].to] == -1)) {
				printf("%d", i + 1);
				if (--sum) printf(" ");
			}
		printf("\n");
	}
	return res;
}

void Work() {
	ans = inf;
	int i, j, source, a, b, c, temp;
	for (i = 0; i < n; i++) {
		source = !i;
		for (j = 0; j < n; j++)
			if (j != i && j != source) {
				temp = Max_Flow(i, source, j, 0);
				if (temp < ans) {
					ans = temp;
					a = i;
					b = source;
					c = j;
				}
			}
	}
	//printf("%d %d %d\n", a, b, c);
	printf("%d\n", ans);
	Max_Flow(a, b, c, 1);
}

int main() {
	while (scanf("%d %d", &n, &m) == 2) {
		Init();
		Work();
	}
	return 0;
}