[Libre OJ]6014「网络流 24 题」最长 k 可重区间集题解

主要思路

这道题还是很妙的,我只想到了最大费用最大流之后就想不动了。

我们在这里介绍边数为\(O(n)\)级别的解法。考虑把所有的端点离散化为\(2n\)个连续的点,然后相邻端点\(i, i+1\)相互连接流量无限、费用为零的边。考虑区间左右端点,左端点连到右端点,流量为\(1\),费用为区间长度。最后源点连左端点,汇点连到右端点。

这样就可以强制满流,且费用最大。

继续阅读[Libre OJ]6014「网络流 24 题」最长 k 可重区间集题解

[Fortuna OJ]Jul 5th – Group A 解题报告 / 集训队互测 2013

A – 家族

这道题真的是送分题(快要想出来直接暴力枚举+并查集的时候去看了题解,最后发现就是这么 sb)。

考虑枚举频段区间\([L, R]\)(将边进行排序,确定下界之后再枚举上界),这个地方是\(O(m^2)\)的。每次枚举下界的时候都要初始化并查集,然后合并两个集合的时候按照大小来修改答案就行了。

继续阅读[Fortuna OJ]Jul 5th – Group A 解题报告 / 集训队互测 2013

网络流

定义

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

基本网络流算法

最大流 – Dinic

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

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

继续阅读网络流

P3980:[NOI2008]志愿者招募题解

解法

我们可以把整个工作流程想像成网络流上的一条链:第\(i\)天连接到第\(i+1\)天的,流量为\(INF – A_i\),费用为\(0\);其中第\(n+1\)连接到汇点,流量为\(INF\),费用为\(0\);源点连接到点\(1\),流量为\(INF\),费用为\(0\)。

对于每一组志愿者\((s_i, t_i, c_i)\),考虑连边\((s_i, t_i + 1, INF, c_i)\),这样意味着整个工作流中可以从额外管道中获取流量,将最大流调整到\(INF\)。

所以求得的最小费用肯定是在最大流量\(INF\)的前提下求得的,即为答案。

继续阅读P3980:[NOI2008]志愿者招募题解

图论学习笔记

强连通分量

一些性质

  1. 有向图中,每一个点仅属于一个强连通分量。
  2. 强连通分量具有传递性。
  3. 极大的强连通分量指的是一个强连通分量无法继续扩大。

Tarjan 算法的一些细节

  1. 当一个节点的 DFN 和 LOW 相等时,则发现了一个强连通分量,进行弾栈。

一些例题

P2002:消息扩散题解

求割点

类似于之前的 Tarjan 算法,只要\(dfn[u]\leq low[u]\),就可以认为这个点是一个割点。理解:下游的点无法除了通过点 u 的路径到达上游 dfn 更小的点,那么这个就是割点。但是还需要考虑点\(u\)为根节点的情况,因为如果点\(u\)为根的话,那么只要子树大于二就算是一个割点,因为子树间的联通必须需要根节点作为枢纽。

模板题代码:

// P3388.cpp
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 20010, MAX_M = 100010;
int head[MAX_N], current, n, m, tmpx, tmpy, low[MAX_N], dfn[MAX_N], tot;
bool ans[MAX_N];
struct edge
{
    int to, nxt;
} edges[MAX_M << 1];
void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}
void tarjan(int u, int fa)
{
    low[u] = dfn[u] = ++tot;
    int child = 0;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        if (!dfn[edges[i].to])
        {
            tarjan(edges[i].to, fa), low[u] = min(low[u], low[edges[i].to]);
            if (low[edges[i].to] >= dfn[u] && u != fa)
                ans[u] = true;
            if (u == fa)
                child++;
        }
        low[u] = min(low[u], dfn[edges[i].to]);
    }
    if (child >= 2 && u == fa)
        ans[u] = true;
}
int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    int cnt = 0;
    for (int i = 1; i <= m; i++)
        scanf("%d%d", &tmpx, &tmpy), addpath(tmpx, tmpy), addpath(tmpy, tmpx);
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i, i);
    for (int i = 1; i <= n; i++)
        if (ans[i])
            cnt++;
    printf("%d\n", cnt);
    for (int i = 1; i <= n; i++)
        if (ans[i])
            printf("%d ", i);
    return 0;
}

双联通分量

点双连通分量

概念:在无向图中,对于点对\(u,v\),在图上删除除\(u,v\)以外的任意一个点,仍然联通,那么称这个点对为点双联通分量。

边双连通分量

概念:在无向图中,对于点对\(u,v\),在图上任意删除一条边,\(u,v\)仍连通,则称其为边双连通分量。

二分图

https://www.renfei.org/blog/bipartite-matching.html

性质

二分图中,选取最少的点数,使这些点和所有的边都有关联(把所有的边的覆盖),叫做最小点覆盖。

二分图最小点覆盖 = 二分图最大匹配

二分图最大点独立集 = 总点数 – 二分图最大总匹配

例题:[USACO2006NOV]Asteriod,[Usaco2005 jan]Muddy Fields

匈牙利算法

模板地址:P3386 【模板】二分图匹配

bool dfs(int u, int tm)
{
    for (int i = head[u]; i != -1; i = edges[i].nxt)
    {
        int to = edges[i].to;
        if (dfn[to] != tm)
        {
            dfn[to] = tm;
            if ((!match[to]) || dfs(match[to], tm))
            {
                match[to] = u;
                return true;
            }
        }
    }
    return false;
}

我个人认为这个是相当精妙的一个写法,可以将“继续匹配”和“向上协商”完美的结合在一起,非常的优秀。

2-SAT

此模型可以用于求出多个条件约束下变量的解集。可以通过某些矛盾关系推出可行关系做有向边,Tarjan 染色即可。

例题:HDU3062:Party 题解