HDU 6214 Smallest Minimum Cut

  • 2018-08-22
  • 15
  • 0

Description:

Consider a network G=(V,E) with source s and sink t. An s-t cut is a partition of nodes set V into two parts such that s and t belong to different parts. The cut set is the subset of E 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).
Each case describes a network G, and the first line contains two integers n (2≤n≤200) and m (0≤m≤1000) indicating the sizes of nodes and edges. All nodes in the network are labelled from 1 to n.
The second line contains two different integers s and t (1≤s,t≤n) corresponding to the source and sink.
Each of the next m lines contains three integers u,v and w (1≤w≤255) describing a directed edge from node u to v with capacity w.

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

题目链接

求最少割边数的最小割。

将每条边权变为C=C*(E+1)+1,E为总边数,跑最大流,MaxFlow%(E+1)即为结果。

具体看:

HDU 6214 Smallest Minimum Cut (最小割最小割边)(两种算法的分析)

AC代码:

评论

还没有任何评论,你来说两句吧