HDU - 6214 Smallest Minimum Cut（最小割边集的最小数量）

Consider a network G=(V,E)G=(V,E) with source ss and sink tt. An s-t cut is a partition of nodes set VV into two parts such that ss and tt belong to different parts. The cut set is the subset of EE with all edges connecting nodes in different parts. A minimum cut is the one whose cut set has the minimum summation of capacities. The size of a cut is the number of edges in the cut set. Please calculate the smallest size of all minimum cuts.

Input

The input contains several test cases and the first line is the total number of cases T (1≤T≤300)T (1≤T≤300). 
Each case describes a network GG, and the first line contains two integers n (2≤n≤200)n (2≤n≤200) and m (0≤m≤1000)m (0≤m≤1000) indicating the sizes of nodes and edges. All nodes in the network are labelled from 11 to nn. 
The second line contains two different integers ss and t (1≤s,t≤n)t (1≤s,t≤n) corresponding to the source and sink. 
Each of the next mm lines contains three integers u,vu,v and w (1≤w≤255)w (1≤w≤255) describing a directed edge from node uu to vv with capacity ww.

Output

For each test case, output the smallest size of all minimum cuts in a line.

Sample Input

2
4 5
1 4
1 2 3
1 3 1
2 3 1
2 4 1
3 4 2
4 5
1 4
1 2 3
1 3 1
2 3 1
2 4 1
3 4 3

Sample Output

2
3

    求最小割边集的最小割边数量的话，一个方法是先进行一遍最大流算法，然后遍历所有边，如果容量用光的话，把他的容量改为1，否则改为inf，然后再进行一边最大流即可，答案就是下次的最大流答案；

#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;
}ed[maxm];
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].ne = head[u]; head[u] = cnt++;
	ed[cnt].v = u, ed[cnt].w = 0;
	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 s = 0; s <= n + 1; s++)
			cur[s] = head[s];
		ans += dfs(st, en, inf);
	}
	return ans;
}
int main() {
	int te;
	scanf("%d", &te);
	while (te--) {
		init();int st, en;
		scanf("%d%d", &n, &m);	
		scanf("%d%d", &st, &en);
		while (m--) {
			int a, b, c;
			scanf("%d%d%d", &a, &b, &c);
			add(a, b, c);
		}
		dinic(st, en);
		for (int s = 0; s < cnt; s+=2) {
			if (ed[s].w == 0) 
				ed[s].w = 1;
			else ed[s].w = inf;
		}
		printf("%d\n", dinic(st, en));
	}
}