UVA - 10480 Sabotage 最大流最小割+ 输出割边集

 因为是pdf形式我就不把题目弄上来了，就写主要需要注意的两点：

 1.输出割边集。正确的写法是先按照源点开始dfs，如果某一边得剩余流量大于0就继续向下探索另一个点并标记，等于零就跳过这一边。最后把所有的边找出来，看看如果有两个点标记不一样（一个标记了一个没标记），就输出这个边就好了（因为我们建立的是双向便所以别忘了遍历时每次加2）。

   但是我在没看这种做法得时候，我是想把所有得剩余流量是0得边输出的，但这样其实不对的。比如1->3(0) 1->4(1) 4->3(1) 3->...这种情况下，虽然1到3剩余流量为0，但其实这是一个点集得，1能够到达3得。

2.*了**了我真是，每次最后都要多加一个换行符，你要是不加返回的不是pe是wa！！

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
const int maxn = 100010;
const int maxm = 1000100;
struct *** {
	int v, w, ne, cap, u;
}ed[maxm];
bool vis[maxn];
int n, m, cnt;
int head[maxn], dis[maxn], cur[maxn];
void init() {
	cnt = 0;
	memset(head, -1, sizeof(head));
}
void add(int u, int v, int w) {
	ed[cnt].v = v; ed[cnt].w = w; ed[cnt].cap = w; ed[cnt].u = u;
	ed[cnt].ne = head[u]; head[u] = cnt++;
	ed[cnt].v = u; ed[cnt].w = w; ed[cnt].cap = w; ed[cnt].u = v;
	ed[cnt].ne = head[v]; head[v] = cnt++;
}
int bfs(int st, int en) {
	queue<int>q;
	memset(dis, 0, sizeof(dis));
	dis[st] = 1;
	q.push(st);
	while (!q.empty()) {
		int u = q.front(); q.pop();
		if (u == en)return 1;
		for (int s = head[u]; ~s; s = ed[s].ne) {
			int v = ed[s].v;
			if (dis[v] == 0 && ed[s].w > 0) {
				dis[v] = dis[u] + 1; q.push(v);
			}
		}
	}
	return dis[en] != 0;
}
int dfs(int st, int en, int flow) {
	int ret = flow, a;
	if (st == en || flow == 0)return flow;
	for (int &s = cur[st]; ~s; s = ed[s].ne) {
		int v = ed[s].v;
		if (dis[v] == dis[st] + 1 && (a = dfs(v, en, min(ret, ed[s].w)))) {
			ed[s].w -= a;
			ed[s ^ 1].w += a;
			ret -= a;
			if (!ret)break;
		}
	}
	if (ret == flow)dis[st] = 0;
	return flow - ret;
}
int dinic(int st,int en) {
	int ans = 0;
	while (bfs(st,en)) {
		for (int i = 0; i <= n + 1; i++)
			cur[i] = head[i];
		ans += dfs(st, en,inf);
	}
	return ans;
}
void find(int st) {
	queue<int>qu;
	qu.push(st);
	memset(vis, 0, sizeof(vis));
	vis[st] = 1;
	while (qu.size()) {
		int u = qu.front(); qu.pop();
		for (int s = head[u]; ~s; s = ed[s].ne) {
			if (ed[s].w > 0) {
				if (!vis[ed[s].v])qu.push(ed[s].v), vis[ed[s].v] = 1;
			}
		}
	}
}
int main() {
	ios::sync_with_stdio(0);
	while (~scanf("%d%d", &n, &m) && n + m) {
		init();
		while (m--) {
			int a, b, c;
			scanf("%d%d%d", &a, &b, &c);
			add(a, b, c);
		}
		memset(vis, 0, sizeof(vis));
		dinic(1, 2);
		find(1);
		for (int s = 0; s < cnt; s++) {
			if (!ed[s].w&&vis[ed[s].u] ^ vis[ed[s].v])cout << ed[s].u << " " << ed[s].v << endl;
		}
		cout << endl;
	}
	return 0;
}