Smallest Minimum Cut HDU - 6214（最小割集）

Smallest Minimum Cut

Time Limit: 2000/2000 MS (Java/Others)    Memory Limit: 65535/32768 K (Java/Others)

Total Submission(s): 2281    Accepted Submission(s): 913

Problem 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   就是求最小割的邊的集合   最小割的邊就等于滿流的邊 1、将每條邊的權值改為w*(m+1)+1, 最後求的最大流除以(m+1)就是原圖的最大流，模上(m+1)就是最小割的邊 2、求得最大流之後，将所有的滿流的邊權設為1，不滿流的邊權設為INF，然後跑一邊最大流就是最小割的邊    

#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <cctype>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define rep(i, a, n) for(int i=a; i<n; i++)
#define lap(i, a, n) for(int i=n; i>=a; i--)
#define lep(i, a, n) for(int i=n; i>a; i--)
#define rd(a) scanf("%d", &a)
#define rlld(a) scanf("%lld", &a)
#define rc(a) scanf("%c", &a)
#define rs(a) scanf("%s", a)
#define MOD 2018
#define LL long long
#define ULL unsigned long long
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _  ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int maxn = 10010, INF = 0x7fffffff;
int head[maxn], cnt;
int d[maxn], vis[maxn], cur[maxn];
int s, t;
struct node
{
    int u, v, c, next;
}Node[maxn<<1];

void add_(int u, int v, int c)
{
    Node[cnt].u = u;
    Node[cnt].v = v;
    Node[cnt].c = c;
    Node[cnt].next = head[u];
    head[u] = cnt++;
}

void add(int u, int v, int c)
{
    add_(u, v, c);
    add_(v, u, 0);
}



void init()
{
    mem(head, -1);
    cnt = 0;
}

bool bfs()
{
    queue<int> Q;
    mem(d, 0);
    Q.push(s);
    d[s] = 1;
    while(!Q.empty())
    {
        int u = Q.front(); Q.pop();
        for(int i=head[u]; i!=-1; i=Node[i].next)
        {
            node e = Node[i];
            if(!d[e.v] && e.c > 0)
            {
                d[e.v] = d[e.u] + 1;
                Q.push(e.v);
                if(e.v == t) return 1;
            }
        }
    }
    return d[t] != 0;
}

int dfs(int u, int cap)
{
    int ret = 0, V;
    if(u==t || cap == 0)
        return cap;
    for(int &i=cur[u]; i!=-1; i=Node[i].next)
    {
        node e = Node[i];
        if(d[e.v] == d[e.u] + 1 && e.c > 0)
        {
            int V = dfs(e.v, min(cap, e.c));
            Node[i].c -= V;
            Node[i^1].c += V;
            ret += V;
            cap -= V;
            if(cap == 0) break;
        }
    }
    if(cap > 0) d[u] = -1;
    return ret;
}

int dinic(int u)
{
    int ans = 0;
    while(bfs())
    {
        memcpy(cur, head, sizeof(head));
        ans += dfs(u, INF);
    }
    return ans;
}

int main()
{
    int T, n, m;
    rd(T);
    while(T--)
    {
        int u, v, c;
        init();
        rd(n); rd(m);
        rd(s), rd(t);
        rep(i, 0, m)
        {
            rd(u), rd(v), rd(c);
            add(u, v, c*(m+1) + 1);
        }

        int res = dinic(s);
        cout<< res % (m+1) <<endl;

    }

    return 0;
}      

轉載于:https://www.cnblogs.com/WTSRUVF/p/9508208.html