[Fortuna OJ]4682「GDOI2017模拟8.11」生物学家

主要思路

这道题原题解作者的思路非常的清晰。我来阐述一下。

首先思考答案的意义,一定是总的权值和减去:

  • 变性花费
  • 不要的赞助费
  • 喝茶费用

我们可以用上面这三个元素组一个网络流,计算最小割使答案最大。

考虑将源点连入雌性,雄性连入雄性,流上限就是变性花费:如果将这种边割掉,那么就是不需要进行变性。考虑朋友的边,如果倾向于变雌性,源点连入,向所有的对应编号连边;如果雄性,连入汇点,所有对应编号的向该朋友连边。

继续阅读[Fortuna OJ]4682「GDOI2017模拟8.11」生物学家

网络流

定义

在有向图中,有唯一的源地(入度为 0)和汇点(出度为 0),每一条边都有非负的容量,且整张图都会保证平衡状态。这样的图叫做网络流图。

基本网络流算法

最大流 – Dinic

每秒钟每条管道流动的液体最多。常用的算法是 Dinic。先做一次 BFS 划分层次,再用 DFS 来进行流动。Dinic 算法就是在网络图上对残存网络进行利用求得最大流。

其中值得一提的是,Dinic 算法中有一个优化方式可以快速求最大流——当前弧优化。当前弧优化可以在每次找残余网络之前记录遍历到的 head 指针,避免不必要的遍历。

继续阅读网络流

[Fortuna OJ]Jul 4th – Group A 解题报告

A – 非回文数字

这道题还没写,是一道数位 DP,推荐记忆化搜索。

B – 管道

这道题是一道相当好的题目。

首先对于\(m = n – 1\)的情况,也就是树的形态下,可以考虑自下向上推,也就是从叶子节点开始推起,参考代码中 Toposort 的写法。然后,对于\(m > n\)的情况可以直接输出\(0\),因为这个方程组并不存在唯一的解:\(m\)个未知数仅提供\(n\)个条件,这样是不成立的。

最后考虑\(m = n\)的情况。这种情况就是基环树了。首先,Toposort 会把支链上的答案全部统计完毕,并且合并到环上的点。最后,我们唯一要多做的事情,就是处理环上的方程组。考虑一个这样的环:

继续阅读[Fortuna OJ]Jul 4th – Group A 解题报告

LibreOJ 6007:「网络流 24 题」方格取数题解

解法

这道题可以看作是网络流的一个模型了。我们把棋盘染色成红色和黑色。然后,源点连红色点,最大流限制为红点的点权;黑点全部连到汇点,最大流限制为黑点的点权。答案为点权总和减去最大流。

我们可以尝试理解一下:对于\(m = 1, n = 2\)的情况:

\[ [ x, y ] \]

那么假设\(x\)为黑点,\(y\)为红点,在网络上是这样的:

我们会发现最大流只会留下较小的一项。这样的话,我们可以感性推广到任何情况,大难点权和减掉最小割就行了。

继续阅读LibreOJ 6007:「网络流 24 题」方格取数题解

LibreOJ 6005:「网络流 24 题」最长递增子序列题解

主要思路

这道题还是很有意思的,建图方式非常的巧妙。首先我们先把第一问的 DP 用 \(O(n \log n)\) 的时间求解一下,顺便搞到一个数组\(f[i]\),含义是以\(i\)为结尾的最长子序列长度。建图的时候要注意的是,每一个位置对应的点要拆成两个:这是为了保持答案的唯一性。所以对于\(f[i]=1\)的点\(i\),连边\((s,i)\);对于\(f[i]=k\)的点\(i\),连边\((i+n,t)\)。之后,如果对于\((u,v), f[v] = f[u] + 1, arr[u] \leq arr[v]\)进行连边,跑个最大流就可以出答案了。

第三问其实跟第二问的差不多,只需要把点\(1\)和点\(n\)的外向边(到源点或者是汇点的边)的最大流限制改成无穷大即可。

继续阅读LibreOJ 6005:「网络流 24 题」最长递增子序列题解

LibreOJ 6002:「网络流 24 题」最小路径覆盖题解

思路

这个模型有点儿牛逼哦。

我们先来建一个网络。我们把我们得到的\(n\)个点复制一遍,变成第\(i\)与第\(i+n\)个点。让源点全部连接点域\([1,n]\)内的点,让点域\([n+1,2n]\)内的点全部连接汇点。如果有边\((u,v)\),连接边\((u,v+n)\)。这里面所有的边容量都是\(1\)。求最大流做差即可。

我们把网络分层(把它想成 3D 的形状),第一层是源点和原生点,第二层是复制点和汇点。这两层之间的边都相当于有向无环图里的单向边,求最大流即可知道哪些不是路径覆盖中的点。

代码

// LOJ6002.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 200 * 3, INF = 0x3f3f3f3f;
int n, m, head[MAX_N], current, upward[MAX_N], s, t, dep[MAX_N], cur[MAX_N], tmpx, tmpy;
bool tag[MAX_N];
struct edge
{
    int to, nxt, weight;
} edges[6000 << 2];
void addpath(int src, int dst, int weight)
{
    edges[current].to = dst, edges[current].weight = weight;
    edges[current].nxt = head[src], head[src] = current++;
}
void add(int src, int dst, int w) { addpath(src, dst, w), addpath(dst, src, 0); }
bool bfs()
{
    memset(dep, 0, sizeof(dep));
    queue<int> q;
    q.push(s), dep[s] = 1;
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (int i = head[u]; i != -1; i = edges[i].nxt)
            if (edges[i].weight > 0 && !dep[edges[i].to])
                q.push(edges[i].to), dep[edges[i].to] = dep[u] + 1;
    }
    return dep[t] != 0;
}
int dfs(int u, int flow)
{
    if (u == t || flow == 0)
        return flow;
    for (int &i = cur[u]; i != -1; i = edges[i].nxt)
        if (edges[i].weight > 0 && dep[edges[i].to] == dep[u] + 1)
        {
            int to = edges[i].to, fl = dfs(to, min(edges[i].weight, flow));
            if (fl > 0)
            {
                upward[u] = edges[i].to;
                if (u != s)
                    tag[edges[i].to - n] = true;
                edges[i].weight -= fl, edges[i ^ 1].weight += fl;
                return fl;
            }
        }
    return 0;
}
int Dinic()
{
    int ans = 0;
    while (bfs())
    {
        for (int i = 1; i <= 2 * n + 2; i++)
            cur[i] = head[i];
        while (int fl = dfs(s, INF))
            ans += fl;
    }
    for (int i = 1; i <= n; i++)
        if (!tag[i])
        {
            int p = i;
            printf("%d ", p);
            while (upward[p] && upward[p] != t)
                printf("%d ", upward[p] - n), p = upward[p] - n;
            printf("\n");
        }
    return ans;
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    s = n * 2 + 1, t = s + 1;
    for (int i = 1; i <= n; i++)
        add(s, i, 1), add(i + n, t, 1);
    for (int i = 1; i <= m; i++)
    {
        scanf("%d%d", &tmpx, &tmpy);
        add(tmpx, tmpy + n, 1);
    }
    printf("%d", n - Dinic());
    return 0;
}