题目描述

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

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

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

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

点的编号从 1 到 n。

输出格式
输出点 S 到点 T 的最大流。

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

数据范围
2≤n≤1000,
1≤m≤10000,
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

(EK求最大流)

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; // important!!!
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;
}

算法2

(ISAP)

C++ 代码

#include<bits/stdc++.h>
using namespace std;
const int inf = 1<<30;
const int N = 1e6+40;
int idx = 1,head[N << 1];
int n,m,s,t;
struct edge
{
    int to;
    int next;
    int val;
}e[N << 1];
void add(int u,int v,int d)
{
    idx++;
    e[idx].to = v;
    e[idx].val = d;
    e[idx].next = head[u];
    head[u] = idx;
}
int dep[N << 1];
int gap[N << 1];
void bfs()
{
    memset(dep,-1,sizeof(dep));
    memset(gap,0,sizeof(gap));
    dep[t] = 0;
    gap[0] = 1;
    queue<int>q;
    q.push(t);
    while(q.size())
    {
        int u = q.front();
        q.pop();
        for(int i = head[u];i;i = e[i].next)
        {
            int v = e[i].to;
            if(dep[v] != -1) continue;
            q.push(v);
            dep[v] = dep[u] + 1;
            gap[dep[v]]++;
        }
    }
    return;
}

int maxflow;

int dfs(int u,int flow)
{
    if(u == t)
    {
        maxflow += flow;
        return flow;
    }
    int used = 0;
    for(int i = head[u];i;i=e[i].next)
    {
        int d = e[i].to;
        if(e[i].val && dep[d] + 1 == dep[u])
        {
            int minn = dfs(d,min(e[i].val,flow - used));
            if(minn)
            {
                e[i].val -= minn;
                e[i ^ 1].val += minn;
                used += minn;
            }
            if(used == flow) return used;
        }
    }
    -- gap[dep[u]];
    if(gap[dep[u]] == 0) dep[s] = n + 1;
    dep[u] ++;
    gap[dep[u]] ++;
    return used;
}
int ISAP()
{
    maxflow = 0;
    bfs();
    while(dep[s] <= n) dfs(s,inf);
    return maxflow;
}
int main()
{   
  scanf("%d%d%d%d",&n,&m,&s,&t);
  for(int i = 1;i <= m; i++)
  {
      int u,v,w;
      scanf("%d%d%d",&u,&v,&w);
      add(u,v,w);
      add(v,u,0);
  }
  printf("%d\n",ISAP());

    return 0;
}