网络流

最大流

给定n个点和若干条有向边，每条边有权值flow[i], 表示第i条边的流量上限.

其中有源点S，只有出边，还有汇点T，只有入边.

对于任意除S和T以外的点x, x的流入和流出的流量总是相等

S流出的总流量等于流入T的总流量.

求S流出的最大流量是多少

暴力：时间复杂度高，可以造一个数据大部分情况都找不到最优解

如何设计最大流的算法？

1. 如何建立纠错机制？

建反边构造, 残余网络

残余网络:每次找完增广路剩下的状态

2. 如何高效的找到增广路？

贪心，优先走最短的边 bfs

上述即为EK算法(Edmonds - Karp)

模板题

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

typedef long long ll;

const ll N = 210, M = 1e4 + 10, INF = 1e18;
int h[N], e[M], w[M], ne[M], idx;
bool st[N];
int pre[N];
ll f[N];
ll maxFlow;

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}

bool bfs(int s, int T)
{
    memset(st, 0, sizeof st);

    queue<int> q;

    q.push(s);

    st[s] = true;
    f[s] = INF;

    while (q.size())
    {
        int t = q.front();
        q.pop();

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            ll W = w[i];

            if (W && !st[j])
            {
                st[j] = true;
                pre[j] = i;

                f[j] = min(f[t], W);

                q.push(j);

                if (j == T) return true;
            }
        }
    }

    return false;
}

void update(int s, int t)
{
    int now = t;
    while (now != s)
    {
        int p = pre[now];

        w[p] -= f[t];
        w[p ^ 1] += f[t];

        now = e[p ^ 1];
    }

    maxFlow += f[t];
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);    

    int n, m, s, t;
    cin >> n >> m >> s >> t;

    memset(h, -1, sizeof h);

    int a, b, c;
    while (m--)
    {
        cin >> a >> b >> c;

        add(a, b, c);
        add(b, a, 0);
    }

    while (bfs(s, t)) update(s, t);

    cout << maxFlow;



    return 0;
}

P2766 最长不下降子序列问题

1. 维护dp[i]表示以第i个数为结尾最长不下降子序列的长度，并找出最大值ans

2. 合法的序列中止下标$i$一定满足dp[i] == ans, 上一个下标 dp[i] = ans - 1

3. 源点s向dp[]为1的点连边, 对于点i, j, 若dp[i] + 1 == dp[j] && a[i] <= a[j] && i < j 那么i向j连边, 所有dp[] == ans的点向汇点t连边

4. 拆点, 边权设为1, 其余边流量设为INF, 跑最大流即为第二问答案;

网络流之最小割问题

对于给定的网络流模型, 其最小割是指删掉边权和最小的边集，使S到T不连通

最小割=最大流

原因是增广路的流量限制就是由最小权值的边决定

最小割的方案不一定唯一