UVA - 10480 Sabotage （最小割 ＋ 输出最小割的边）

The regime of a small but wealthy * has been abruptly overthrown by an unexpected rebellion. Because of the enormous disturbances this is causing in world economy, an imperialist military
super power has decided to invade the country and reinstall the old regime.
For this operation to be successful, communication between the capital and the largest city must
be completely cut. This is a difficult task, since all cities in the country are connected by a computer
network using the Internet Protocol, which allows messages to take any path through the network.
Because of this, the network must be completely split in two parts, with the capital in one part and
the largest city in the other, and with no connections between the parts.
There are large differences in the costs of sabotaging different connections, since some are much
more easy to get to than others.
Write a program that, given a network specification and the costs of sabotaging each connection,
determines which connections to cut in order to separate the capital and the largest city to the lowest
possible cost.
Input
Input file contains several sets of input. The description of each set is given below.
The first line of each set has two integers, separated by a space: First one the number of cities, n in
the network, which is at most 50. The second one is the total number of connections, m, at most 500.
The following m lines specify the connections. Each line has three parts separated by spaces: The
first two are the cities tied together by that connection (numbers in the range 1 − n). Then follows the
cost of cutting the connection (an integer in the range 1 to 40000000). Each pair of cites can appear
at most once in this list.
Input is terminated by a case where values of n and m are zero. This case should not be processed.
For every input set the capital is city number 1, and the largest city is number 2.
Output
For each set of input you should produce several lines of output. The description of output for each set
of input is given below:
The output for each set should be the pairs of cities (i.e. numbers) between which the connection
should be cut (in any order), each pair on one line with the numbers separated by a space. If there is
more than one solution, any one of them will do.
Print a blank line after the output for each set of input.
Sample Input
5 8
1 4 30
1 3 70
5 3 20
4 3 5
4 5 15
5 2 10
3 2 25
2 4 50
5 8
1 4 30
1 3 70
5 3 20
4 3 5
4 5 15
5 2 10
3 2 25
2 4 50
0 0
Sample Output
4 1
3 4
3 5
3 2
4 1
3 4
3 5
3 2

题目大意：

给你一个无向图，让你从中选一些边切割掉，让1和2两个点不连通。
并输出切割掉的边。

解题思路：

题目就是求1，2间的最小割，也就是求最大流。
关键问题是如何输出呢？
我们跑完网络流之后，在参与网络里，从1 点出发，能到的点是一个集合X，不能到的点是Y，然后遍历所有的边，如果这条边的两个点，一个在集合X里，一个在集合Y里，就说明这条边是割边（残余流量为0了）。

注意：别忘输出一个空行。

AC代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <algorithm>
#define inf 0x3f3f3f3f
using namespace std;
const int maxn = 1e5+10;
int n,m;//n是点数，m是边数
int sp,tp;//原点 汇点
int one[maxn];
int U[maxn],V[maxn];
struct node{
	int to;
	int w;
	int next;
}side[maxn*10];
int head[maxn],cnt = 0;
int deep[maxn];//每个点的层数
int cur[maxn];//当前弧优化
void init(){
	memset(head,-1,sizeof(head));
	cnt = 0;
}
void add(int x,int y,int w){
	side[cnt].to = y;
	side[cnt].w = w;
	side[cnt].next = head[x];
	head[x] = cnt++;
}
//分层
bool bfs(){
	memset(deep,-1,sizeof(deep));
	queue<int> q;
	q.push(sp);//放入原点
	deep[sp] = 0;
	while(q.size()){
		int now = q.front();
		q.pop();
		for(int i=head[now];i!=-1;i=side[i].next){
			int to = side[i].to;
			if(deep[to]==-1&&side[i].w>0){
				deep[to] = deep[now]+1;
				q.push(to);
				if(to == tp) break;
			}
		}
	}
	return deep[tp]!=-1;
}
//找增广路 u是当前节点 cap是当前的流量
int dfs(int u,int cap){
	if(u==tp||cap==0) return cap;
	int res = 0;
	int f;
	for(int &i=cur[u];i!=-1;i=side[i].next){
		int to = side[i].to;
		//多路增广优化
		if(deep[to] ==deep[u]+1&&(f=dfs(to,min(cap-res,side[i].w)))>0){
			side[i].w -=f;
			side[i^1].w += f;
			res += f;
			if(res == cap) return cap;
		}
	}
	if(!res) deep[u] = -1;//这个点废了,炸点优化
	return res;
}
int Dinic(){
	int ans = 0;
	while(bfs()){
		for(int i=1;i<=n;i++) cur[i] =head[i];
		ans += dfs(sp,inf);
	}
	return ans;
}

void dfs_2(int x){
	one[x] = 1;
	for(int i=head[x];i!=-1;i=side[i].next){
		int to = side[i].to;
		if(one[to]) continue;
		if(side[i].w>0){
			one[to] = 1;
			dfs_2(to);
		}
	
	}
}
int main(){
	while(~scanf("%d%d",&n,&m)){
		if(n==0&&m==0) break;
		init();
		for(int i=0;i<m;i++){
			int u,v,w;
			scanf("%d%d%d",&u,&v,&w);
			add(u,v,w);
			add(v,u,0);
			add(v,u,w);
			add(u,v,0);
			U[i] = u;
			V[i] = v;
		}
		sp = 1,tp = 2;
		Dinic();
		memset(one,0,sizeof(one));
		dfs_2(1);
		for(int i=0;i<m;i++){
			if((one[U[i]]&&!one[V[i]])||(one[V[i]]&&!one[U[i]])){
				cout<<U[i]<<" "<<V[i]<<endl;
			}
		} 
		cout<<endl;
	}
	
	
	return 0;
}