题目描述

给定一个包含 n 个点 m 条边的有向图，并给定每条边的容量，边的容量非负。

图中可能存在重边和自环。求从点 S 到点 T 的最小割。

输入格式
第一行包含四个整数 n,m,S,T。

接下来 m 行，每行三个整数 u,v,c，表示从点 u 到点 v 存在一条有向边，容量为 c。

点的编号从 1 到 n。

输出格式
输出点 S 到点 T 的最小割。

如果从点 S 无法到达点 T 则输出 0。

数据范围
2≤n≤10000,
1≤m≤100000,
0≤c≤10000,
S≠T

样例

7 14 1 7
1 2 5
1 3 6
1 4 5
2 3 2
2 5 3
3 2 2
3 4 3
3 5 3
3 6 7
4 6 5
5 6 1
6 5 1
5 7 8
6 7 7
输出样例：
14

算法1

(暴力枚举)

C++ 代码

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 1e6 + 40,E = 2e7 + 10;

struct egde{
    ll next;
    ll val;
    ll to;
}e[N << 1];

int n,m,s,t;
ll ans = 0;
ll idx = 1;
int head[N << 1];

void add(int u , int v, ll w)
{
    idx ++;
    e[idx].val = w;
    e[idx].to = v;
    e[idx].next = head[u];
    head[u] = idx;
}

int dep[N << 1];
queue<int>q;

bool bfs()
{
    memset(dep, 0, sizeof(dep));
    q.push(s);
    dep[s] = 1;
    while(q.size())
    {
        int u = q.front();
        q.pop();
        for(int i = head[u]; i; i = e[i].next)
        {
            int x = e[i].to;
            if(e[i].val && !dep[x])
            {
                dep[x] = dep[u] + 1;
                q.push(x);
            }
        }
    }
    return dep[t];
}

ll dfs(int u,ll in)
{
    if(u == t)
    return in;
    ll out = 0;
    for(int i = head[u]; i; i = e[i].next)
    {
        int v = e[i].to;
        if(e[i].val && dep[v] == dep[u] + 1)
        {
            ll res = dfs(v, min(e[i].val, in));
            e[i].val -= res;
            e[i ^ 1].val += res;
            in -= res;
            out += res;
        }
    }
    if( out == 0 ) dep[u] = 0;
    return out;
}

int main()
{
    scanf("%d%d%d%d",&n,&m,&s,&t);
    for(int i = 1;i <= m ;i ++) 
    {
         int u ,v;
         ll w;
         scanf("%d%d%lld",&u,&v,&w);
         add(u,v,w);
         add(v,u,0);
    }
    while(bfs())
    {
        ans += dfs(s, 1e8);
    }
    printf("%lld\n",ans);
    return 0;
}