HDU 6214 Smallest Minimum Cut （最小割）

HDU 6214 Smallest Minimum Cut （最小割）

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

24 51 41 2 31 3 12 3 12 4 13 4 24 51 41 2 31 3 12 3 12 4 13 4 3

Sample Output

23

题意

求图中最小割的前提下的最少边数。

思路

经典的题目啦，我们把一条边的大小附加到该边的流量中，然后求出此时的最大流，流中即包含了所选择的边数。

另外：最大流 = 最小割

AC 代码

#includeusing namespace std;typedef __int64 LL;const int MAXN=10000;const int MAXM=10000;const int INF=0x3f3f3f3f;struct Node{ int from,to,next; int cap;} edge[MAXM];int tol;int head[MAXN];int dep[MAXN];int gap[MAXN];int n;void init(){ tol=0; memset(head,-1,sizeof(head));}void addedge(int u,int v,int w){ edge[tol].from=u; edge[tol].to=v; edge[tol].cap=w; edge[tol].next=head[u]; head[u]=tol++; edge[tol].from=v; edge[tol].to=u; edge[tol].cap=0; edge[tol].next=head[v]; head[v]=tol++;}void BFS(int start,int end){ memset(dep,-1,sizeof(dep)); memset(gap,0,sizeof(gap)); gap[0]=1; int que[MAXN]; int front,rear; front=rear=0; dep[end]=0; que[rear++]=end; while(front!=rear) { int u=que[front++]; if(front==MAXN)front=0; for(int i=head[u]; i!=-1; i=edge[i].next) { int v=edge[i].to; if(dep[v]!=-1)continue; que[rear++]=v; if(rear==MAXN)rear=0; dep[v]=dep[u]+1; ++gap[dep[v]]; } }}int SAP(int start,int end){ int res=0; BFS(start,end); int cur[MAXN]; int S[MAXN]; int top=0; memcpy(cur,head,sizeof(head)); int u=start; int i; while(dep[start]edge[S[i]].cap) { temp=edge[S[i]].cap; inser=i; } for(i=0; idep[edge[i].to]) { min=dep[edge[i].to]; cur[u]=i; } } --gap[dep[u]]; dep[u]=min+1; ++gap[dep[u]]; if(u!=start)u=edge[S[--top]].from; } } return res;}template inline void scan_d(T &ret){ char c; ret = 0; while ((c = getchar()) < '0' || c > '9'); while (c >= '0' && c <= '9') { ret = ret * 10 + (c - '0'), c = getchar(); }}template inline void print_d(T x){ if (x > 9) { print_d(x / 10); } putchar(x % 10 + '0');}int main(){ int T; scan_d(T); while(T--) { int m,st,ed; scan_d(n); scan_d(m); scan_d(st); scan_d(ed); init(); for(int i=0; i

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。