头像

小小_88




离线:10小时前


最近来访(246)
用户头像
菜狗一枚
用户头像
liiyii
用户头像
Hard_IINE
用户头像
hncsxzx
用户头像
雨天的尾巴
用户头像
yxc
用户头像
Aigrl
用户头像
忒斯底律
用户头像
lihua777
用户头像
222222
用户头像
Reminiscence
用户头像
天蝎座的流星
用户头像
H.Y.Z
用户头像
korokseeds
用户头像
陌上花开Charlie
用户头像
北海没有WA
用户头像
流苏贺风
用户头像
Happy_GG
用户头像
爱算法爱生活
用户头像
Axehco


围栏障碍训练场

C++ 代码

/*
本题是一个求最优方案的问题,可以考虑用 dp 来做。

由于每一次走到围栏上都要选择往左端点走或往右端点走,因此我们用两个状态来表示。

设 f[i][0] 表示从第 i 个围栏的左端点出发,到达终点的最短横向距离
设 f[i][1] 表示从第 i 个围栏的右端点出发,到达终点的最短横向距离

假设当前在第 i 层的左端点,往下走到第一个包含第 i 层左端点的围栏 j(并非只能走到下一层,而是往下走到第一个碰到的围栏),
那么可以直接从第 i 层的左端点走到第 j 层,再横着走到第 j 层的左端点或右端点。从第 i 层的右端点走则同理。

f[i][0] = min(f[j][0] + abs(l[i] - l[j]), f[j][1] + abs(l[i] - r[j]))
f[i][1] = min(f[j][0] + abs(r[i] - l[j]), f[j][1] + abs(r[i] - r[j]))

注意!两个状态转移方程中的 j 不一定是同一个,而是从左端点或右端点往下走第一个碰到的围栏

为了保证在到达终点,我们规定终点所在层数为第 0 层,且 l[0] = r[0] = 0,保证最终一定走到终点

结束状态为 min(f[n][0] + abs(l[n] - s), f[n][1] + abs(r[n] - s))

现在的问题就是如何快速找到决策 j,我们可以用线段树来维护每个点最后一次覆盖的区间,这样就能快速查询获得

另外,由于区间是包含负区间的,所以我们将所有坐标加上一个偏移量,不影响结果
*/

#include <iostream>
#include <cstring>

using namespace std;

const int N = 50010, M = 200010, X = 100000;

int n, s;
int l[N], r[N]; //记录每个区间的左、右端点
//设 f[i][0] 表示从第 i 个围栏的左端点出发,到达终点的最短横向距离
//设 f[i][1] 表示从第 i 个围栏的右端点出发,到达终点的最短横向距离
int f[N][2];

struct Node
{
    int l, r;
    int x; //记录最后一次覆盖的区间(懒标记)
}tr[M * 4]; //线段树

void build(int u, int l, int r) //初始化线段树
{
    if(l == r) tr[u] = {l, r, 0};
    else
    {
        tr[u] = {l, r, -1};
        int mid = l + r >> 1;
        build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    }
}

void pushdown(int u) //将懒标记下传
{
    if(tr[u].l != tr[u].r && tr[u].x != -1)
    {
        tr[u << 1].x = tr[u << 1 | 1].x = tr[u].x;
        tr[u].x = -1;
    }
}

void modify(int u, int l, int r, int x) //将 [l ~ r] 往下第一个走到的区间修改为 x
{
    if(tr[u].l >= l && tr[u].r <= r)
    {
        tr[u].x = x;
        return;
    }

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if(l <= mid) modify(u << 1, l, r, x);
    if(r > mid) modify(u << 1 | 1, l, r, x);
}

int query(int u, int x) //查询 x 往下第一个走到的区间
{
    if(tr[u].l == tr[u].r) return tr[u].x;

    pushdown(u);
    int mid = tr[u].l + tr[u].r >> 1;
    if(x <= mid) return query(u << 1, x);
    else return query(u << 1 | 1, x);
}

int main()
{
    scanf("%d%d", &n, &s);

    build(1, 0, X * 2); //初始化线段树

    //所有坐标加上偏移量 X
    l[0] = r[0] = X; //设置终点所在的区间的左、右端点都在终点
    s += X;
    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d", &l[i], &r[i]);
        l[i] += X, r[i] += X;

        int j = query(1, l[i]); //查询左端点往下第一个走到的区间
        f[i][0] = min(f[j][0] + abs(l[i] - l[j]), f[j][1] + abs(l[i] - r[j])); //状态转移方程
        j = query(1, r[i]); //查询右端点往下第一个走到的区间
        f[i][1] = min(f[j][0] + abs(r[i] - l[j]), f[j][1] + abs(r[i] - r[j])); //状态转移方程
        modify(1, l[i], r[i], i); //修改 l[i] ~ r[i] 往下第一个走到的区间
    }
    printf("%d\n", min(f[n][0] + abs(l[n] - s), f[n][1] + abs(r[n] - s)));

    return 0;
}



芯片

C++ 代码

/*
本题是一个求摆放方案数的问题,并且数据不大,因此可以用状态压缩 dp 来做。

设 f[i][j] 表示前 i 行放置芯片,且第 i 行的状态为 j 的最大放置数

这里可以发现,一个芯片可能是竖着摆放的,最多会占用三行,因此对于第 i 行,我们要实时的知道前两行的状态。
可以用一个三进制数来表示每一个状态 j,对于每一位 k,为 0 表示 (i, k) 和 (i-1, k) 都可用,为 1 表示 (i, k)
可用,(i-1, k) 不可用,为 2 表示 (i, k) 和 (i-1, k) 都不可用。

这样对于第 i 行的状态,我们还能得出第 i - 1 行的状态,而对于第 i - 1 行的状态,我们还能得出第 i - 2 行的状态,
因此我们可以通过两行的状态得到三行的状态。

三进制数我们没法直接表示,这里可以用一个数组来记录三进制数,用两个函数来进行三进制数和十进制数之间的转化。

状态转移方程并不好统计,因此可以在第 i 行枚举以每一个点为芯片的左下角来进行搜索,这样能保证搜索到所有情况
*/

#include <iostream>
#include <cstring>

using namespace std;

const int N = 155, M = 15;

int n, m, k;
//设 f[i][j] 表示在前 i 行放置芯片,且第 i 行的状态为 j 的最大放置数,状态 j 是一个三进制数
//第 k 位是 0 表示 (i, k) 和 (i-1, k) 都可用,1 表示 (i, k) 可用,(i-1, k) 不可用,2 表示 (i, k) 和 (i-1, k) 都不可用
int f[2][60000];
int pre[M], now[M]; //记录当前行的三进制状态、上一行的三进制状态
bool st[N][M]; //设 st[i][j] 表示第 i 行第 j 列的格子是否可用,true 表示坏了,false 表示没坏
int pow3[M] = {1, 3, 9, 27, 81, 243, 729, 2187, 6561, 19683, 59049}; //设 pow3[i] 表示 3 的 i 次方

int three_ten(int a[]) //将三进制状态转化成十进制状态
{
    int res = 0; //记录转化后的十进制数
    for(int i = 0; i < m; i++) res += a[i] * pow3[i];
    return res;
}

void ten_three(int x, int (&a)[M]) //将十进制状态转化成三进制状态,并放入 a 数组中
{
    for(int i = 0; i < m; i++)
    {
        a[i] = x % 3;
        x /= 3;
    }
}

//爆搜得到前 i 行摆放芯片的方案数
//尝试以 (i, j) 为芯片的左下角进行摆放,last 为上一行的方案数,state 为当前行的状态
void dfs(int i, int j, int last, int state)
{
    f[i & 1][state] = max(f[i & 1][state], last); //更新状态

    if(j >= m) return; //列数超出范围,结束当前分支

    //竖着放芯片
    if(j + 1 < m && !pre[j] && !pre[j + 1] && !now[j] && !now[j + 1])
    {
        now[j] = now[j + 1] = 2; //摆放芯片后更新状态
        dfs(i, j + 2, last + 1, three_ten(now)); //继续搜索
        now[j] = now[j + 1] = 0; //还原状态
    }

    //横着放芯片
    if(j + 2 < m && !now[j] && !now[j + 1] && !now[j + 2])
    {
        now[j] = now[j + 1] = now[j + 2] = 2; //拜访芯片后更新状态
        dfs(i, j + 3, last + 1, three_ten(now)); //继续搜索
        now[j] = now[j + 1] = now[j + 2] = 0; //还原状态
    }

    //不放芯片
    dfs(i, j + 1, last, state);
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d%d", &n, &m, &k);

        memset(st, 0, sizeof st); //初始化
        while(k--)
        {
            int x, y;
            scanf("%d%d", &x, &y);
            st[x][y - 1] = true; //行数从 1 开始,列数从 0 开始
        }

        memset(f[1 & 1], -1, sizeof f[1 & 1]); //初始化第一行的状态,-1 表示无法转移
        for(int i = 0; i < m; i++) pre[i] = st[1][i] ? 2 : 1; //记录第一行的状态,由于是第一行,所以上一行不可用
        int temp = three_ten(pre); //将第一行的三进制状态转化成十进制
        f[1 & 1][temp] = 0; //第一行不能摆放芯片,方案数是 0
        for(int i = 2; i <= n; i++) //枚举行数(第一行已经处理)
        {
            memset(f[i & 1], -1, sizeof f[i & 1]); //初始化当前行的状态
            for(int j = 0; j < pow3[m]; j++) //枚举上一行的十进制状态
            {
                if(f[(i - 1) & 1][j] == -1) continue; //如果上一行状态不可转移,直接跳过
                ten_three(j, pre); //将上一行的十进制状态转化成三进制状态
                for(int k = 0; k < m; k++) //记录当前行的状态
                    if(st[i][k]) now[k] = 2; //当前格子不可用,状态为 2
                    else now[k] = pre[k] ? pre[k] - 1 : 0; //当前格子可用,根据上一行来记录当前状态
                temp = three_ten(now); //将当前行的三进制状态转化成十进制状态
                dfs(i & 1, 0, f[(i - 1) & 1][j], temp); //用爆搜来得到前 i 行摆放芯片的方案数
            }
        }

        int res = 0; //记录总方案数
        for(int i = 0; i < pow3[m]; i++) res = max(res, f[n & 1][i]); //枚举第 n 行的所有状态,取最大值
        printf("%d\n", res);
    }
    return 0;
}



玉米田

C++ 代码

/*
本题是一个田中摆放方案问题,而且数据非常小,可以用状压 dp 来做。

设 f[i][j] 表示前 i 行种植玉米,且第 i 行的种植状态为二进制数 j,能种植玉米的方案数,
j 的每一位表示第 i 行的每一列是否种植玉米,1 表示种植,0表示不种植

要求所有玉米不能相邻,若第 i - 1 行的状态为 j,第 i 行的状态为 k,那么要求第 i - 1 行种植玉米的位置,
第 i 行在同一个位置上不能种植玉米,即 j & k == 0

同一行中也不能有相邻的玉米,对应到二进制数的表示上就是不能有相邻的 1,这样的状态比较少,我们可以提前预处理出来。

田中还有不能种植玉米的位置,为了方便,我们将田里的状态也用二进制表示,第 i 个二进制数的第 j 位表示第 i 行第 j 
列的田地状态,为 0 表示能种植,为 1 表示不能种植,假设第 i 行的田地状态为 k,种植状态为 j,那么要求 j & k == 0

综上分析得状态转移方程:f[i][j] += f[i - 1][k] (j & k == 0)

状态转移方程比较简单,对二进制数的一些处理都可以进行预处理。
*/

#include <iostream>
#include <cstring>
#include <vector>

using namespace std;


const int N = 14, M = 1 << N, mod = 1e8;

int n, m;
int g[N];
int f[N][M]; //设 f[i][j] 表示前 i 行种植玉米,且第 i 行的种植状态为二进制数 j,能种植玉米的方案数
vector<int> state; //记录所有不存在相邻两个 1 的二进制数
vector<int> head[M]; //head[state] 中所有的状态 k 都保证 k & state == 0

bool check(int state) //判断 state 是否满足不存在相邻两个 1
{
    for(int i = 0; i < m; i++)
        if((state >> i & 1) && (state >> i + 1 & 1))
            return false; //存在相邻两个 1,不满足
    return true; //满足
}

void init() //预处理 state, head
{
    //预处理 state
    for(int i = 0; i < 1 << m; i++)
        if(check(i))
            state.push_back(i); //如果当前状态不存在相邻两个 1,存储起来

    //预处理 head
    for(int i = 0; i < state.size(); i++)
        for(int j = 0; j < state.size(); j++)
            if((state[i] & state[j]) == 0)
                head[i].push_back(j);
}

int main()
{
    scanf("%d%d", &n, &m);

    //构建地图
    for(int i = 1; i <= n; i++)
        for(int j = 0; j < m; j++)
        {
            int x;
            scanf("%d", &x);
            g[i] += !x << j; //能种植为 0,不能种植为 1
        }

    init(); //预处理 state, head

    //状态压缩 dp
    f[0][0] = 1; //初始化
    for(int i = 1; i <= n + 1; i++)
        for(int j = 0; j < state.size(); j++)
            for(int k = 0; k < head[j].size(); k++)
            {
                if(g[i] & state[j]) continue; //和地图冲突说明不合法,直接跳过
                f[i][j] = (f[i][j] + f[i - 1][head[j][k]]) % mod; //状态转移方程
            }
    printf("%d\n", f[n + 1][0]);

    return 0;
}



光之大陆问题

解题思路

给我们 $n$ 个点的无向完全图,然后要我们每次从中选取一些边,使得整张图连通,且只包含简单环,问我们有多少种合法的选取方案。

可以将方案拆分然后用乘法原理来解。

我们先统计一下把 $n$ 个点分成 $m$ 个环,有多少种方案。

再对于上一步的每一种方案,把这 $m$ 个环拼成一个生成树,有多少种方案。

对于第二步,结合 Prufer 编码,如果每次去掉一个部分,Prufer 编码的长度会是 $m - 2$,然后对于每个删去的环,由于这个环相邻的环内部会有很多点,我们删去的这个环可能连接任意一个点,这都会导致我们输出的 Prufer 编码不同,每次的输出都可能有 $n$ 种,因此 $n$ 个点分成 $m$ 个环能拼成的生成树的方案是 $n^{m-2}$ 种

接下来的需要知道第一步的方案数,即把 $n$ 个点分成 $m$ 个环的方案数。这里就要用计数类 dp 来求了。

设 $f[i][j]$ 表示把 $i$ 个点分成 $j$ 个环的方案数。

对于计数类 dp,我们通常需要围绕一个 “基准点” 来求,能避免子问题之间的重叠。我们以 $1$ 号点为 “基准点”,枚举 $1$ 号点所在的环的大小 $k$,从 $2 \sim i$ 这 $i - 1$ 个节点中选 $k - 1$ 个,然后对于 $k$ 个点的圆环,内部又有若干种组合方案,首先 $k$ 个点的排列有 $k!$ 种,且对称的和旋转的其实都是都一种,因此内部方案数为 $\frac{k!}{2*k}=\frac{(k-1)!}{2}$,并且这个环还需要连出来一条边用来和图中其他部分相连,这条边的选择也会有 $k$ 种,所以得出整个的方案数为 $f[i-k][j-1] * C_{i-1}^{k-1} * \frac{k!}{2}$

得出状态转移方程为:$f[i][j] = \sum_{k=1}^{i-j+1} f[i-k][j-1] * C_{i-1}^{k-1} * \frac{k!}{2}$

求出所有的 $f[i][j]$ 后,枚举一下分成的环的数量 $k$,分成 $k$ 个环的方案数是 $f[n][k]$,$k$ 个环拼成生成树的方案数是 $n^{k-2}$,所以最终答案就是 $\sum_{k=1}^{n} f[n][k] * n^{k-2}$。

注意,这里还有特殊情况需要处理,对于 $k$ 个点的环,由于还有向外连的一条边,所以我们求的方案数为 $\frac{(k-1)!}{2} *k = \frac{k!}{2}$,但是当 $k=1$ 时,也就是只有一个 $n$ 个节点的环时,我们没有向外连的这条边,且不需要求第二步,所以总方案数直接就是 $\frac{(n-1)!}{2}$

另外,由于本题是无向图且不存在重边,因此两个点之间是不存在环的,也需要特判一下


C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 210;

int n, m;
int C[N][N]; //C(a, b)
int g[N]; //g[k] = k! / 2
int f[N][N]; //设 f[i][j] 表示把 i 个点分成 j 个环的方案数

void init() //预处理 C[][], g[]
{
    //预处理 C[][]
    for(int i = 0; i < n; i++)
        for(int j = 0; j <= i; j++)
            if(!j) C[i][j] = 1;
            else C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % m;

    //预处理 g[]
    g[1] = 1, g[2] = 0, g[3] = 3;
    for(int i = 4; i <= n; i++) g[i] = g[i - 1] * i % m; //g[3] 已经除 2,后面都是乘法递推,除 2 是继承的
}

int main()
{
    scanf("%d%d", &n, &m);

    init(); //预处理 C[][], g[]

    //dp
    f[0][0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++)
            for(int k = 1; k <= i - j + 1; k++)
                f[i][j] = (f[i][j] + (LL)f[i - k][j - 1] * C[i - 1][k - 1] * g[k]) % m; //状态转移方程

    int res = g[n - 1]; //统计总方案数,k = 1 时的方案数单独计算
    int p = 1; //记录 n 的 k - 2 次方
    for(int k = 2; k <= n; k++)
    {
        res = (res + (LL)f[n][k] * p) % m;
        p = (LL)p * n % m;
    }
    printf("%d\n", res);

    return 0;
}


活动打卡代码 AcWing 2418. 光之大陆

#include <iostream>
#include <cstring>

using namespace std;

typedef long long LL;

const int N = 210;

int n, m;
int C[N][N]; //C(a, b)
int g[N]; //g[k] = k! / 2
int f[N][N]; //设 f[i][j] 表示把 i 个点分成 j 个环的方案数

void init() //预处理 C[][], g[]
{
    //预处理 C[][]
    for(int i = 0; i < n; i++)
        for(int j = 0; j <= i; j++)
            if(!j) C[i][j] = 1;
            else C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % m;

    //预处理 g[]
    g[1] = 1, g[2] = 0, g[3] = 3;
    for(int i = 4; i <= n; i++) g[i] = g[i - 1] * i % m; //g[3] 已经除 2,后面都是乘法递推,除 2 是继承的
}

int main()
{
    scanf("%d%d", &n, &m);

    init(); //预处理 C[][], g[]

    //dp
    f[0][0] = 1;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= i; j++)
            for(int k = 1; k <= i - j + 1; k++)
                f[i][j] = (f[i][j] + (LL)f[i - k][j - 1] * C[i - 1][k - 1] * g[k]) % m; //状态转移方程

    int res = g[n - 1]; //统计总方案数,k = 1 时的方案数单独计算
    int p = 1; //记录 n 的 k - 2 次方
    for(int k = 2; k <= n; k++)
    {
        res = (res + (LL)f[n][k] * p) % m;
        p = (LL)p * n % m;
    }
    printf("%d\n", res);

    return 0;
}


活动打卡代码 AcWing 2419. prufer序列

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;

int n, m;
int f[N]; //记录把 n 看作根节点,每个节点的父节点
int d[N]; //记录每个节点的出度
int p[N]; //记录 Prufer 编码

void tree2prufer() //无根树转化成 Prufer 编码
{
    for(int i = 1; i < n; i++)
    {
        scanf("%d", &f[i]);
        d[f[i]]++; //出度 + 1
    }

    for(int i = 0, j = 1; i < n - 2; j++)
    {
        while(d[j]) j++; //找到第一个叶节点
        p[i++] = f[j]; //输出相邻节点
        //如果删除当前最小叶节点后,它的父节点刚好是编号最小的叶节点,直接输出
        while(i < n - 2 && --d[p[i - 1]] == 0 && p[i - 1] < j) p[i++] = f[p[i - 1]];
    }

    for(int i = 0; i < n - 2; i++) printf("%d ", p[i]);
}

void prufer2tree() //Prufer 编码转化成无根树
{
    for(int i = 1; i <= n - 2; i++)
    {
        scanf("%d", &p[i]);
        d[p[i]]++; //每个点的出度就是它在 Prufer 编码中出现的次数
    }
    p[n - 1] = n; //Prufer 序列中最后一个数一定是 n

    for(int i = 1, j = 1; i < n; i++, j++)
    {
        while(d[j]) j++; //找到第一个叶节点
        f[j] = p[i]; //j 的父节点就是 p[i]
        //如果删除 j 后,j 的父节点更好是编号最小的叶节点,继续给他配对父节点
        while(i < n - 1 && --d[p[i]] == 0 && p[i] < j) f[p[i]] = p[i + 1], i++;
    }

    for(int i = 1; i <= n - 1; i++) printf("%d ", f[i]);
}

int main()
{
    scanf("%d%d", &n, &m);

    if(m == 1) tree2prufer(); //无根树转化成 Prufer 编码
    else prufer2tree(); //Prufer 编码转化成无根树

    return 0;
}



指挥网络问题

解题思路

关于朱刘算法请参考前置知识:最小树形图算法的相关概念

本题是一个有向图的最小生成树问题,是朱刘算法的模板题,直接套模板即可。


C++ 代码

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

typedef pair<double, double> PDD;

const int N = 110;
const double INF = 1e8;

int n, m;
PDD a[N]; //记录所有点的坐标
bool g[N][N]; //邻接矩阵
double d[N][N], bd[N][N]; //记录每两个点之间的距离、备份
int pre[N]; //记录每个点选择的前驱点
int dfn[N], low[N], timestamp; //tarjan 算法的数组
int stk[N], top; //栈
bool in_stk[N]; //记录每个点是否在栈中
int id[N], cnt; //记录每个点所在的强连通分量编号
bool st[N]; //记录每个点能否从 1 号点搜索到

void dfs(int u) //从 u 节点往下搜索所有点
{
    st[u] = true;

    for(int i = 1; i <= n; i++)
        if(g[u][i] && !st[i])
            dfs(i);
}

bool check() //判断整个图是否具有连通性
{
    memset(st, 0, sizeof st); //初始化
    dfs(1); //从 1 号点开始搜索所有点

    for(int i = 1; i <= n; i++)
        if(!st[i])
            return false; //如果某个点搜不到,说明图不连通
    return true; //否则说明连通
}

double get_dist(int i, int j) //计算两个点之间的距离
{
    double x = a[i].first - a[j].first;
    double y = a[i].second - a[j].second;
    return sqrt(x * x + y * y);
}

void tarjan(int u) //tarjan 算法缩点
{
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u, in_stk[u] = true;

    //由于每个点只有一条入边,不需要循环
    int j = pre[u];
    if(!dfn[j])
    {
        tarjan(j);
        low[u] = min(low[u], low[j]);
    }
    else if(in_stk[j]) low[u] = min(low[u], dfn[j]);

    //找到一个环
    if(dfn[u] == low[u])
    {
        int y;
        cnt++;
        do
        {
            y = stk[top--];
            in_stk[y] = false;
            id[y] = cnt;
        } while(y != u);
    }
}

double work() //计算答案
{
    double res = 0; //记录答案

    //计算每两个点之间的距离
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(g[i][j]) d[i][j] = get_dist(i, j); //存在边,计算距离
            else d[i][j] = INF; //不存在边,距离为 INF

    //朱刘算法
    while(true)
    {
        //对于每个点,选择它所有入边中最小的一条边
        for(int i = 1; i <= n; i++)
        {
            pre[i] = i;
            for(int j = 1; j <= n; j++)
                if(d[pre[i]][i] > d[j][i]) //如果边更小,更换
                    pre[i] = j;
        }

        //初始化
        memset(dfn, 0, sizeof dfn);
        timestamp = top = cnt = 0;

        //tarjan 算法求环
        for(int i = 1; i <= n; i++)
            if(!dfn[i])
                tarjan(i);

        if(cnt == n) //如果缩点后还是 n 个点,说明不存在环
        {
            for(int i = 2; i <= n; i++) res += d[pre[i]][i]; //累加所有选中的边的权值
            break;
        }

        //否则说明有环,将环内所有边的权值累加到答案中
        for(int i = 2; i <= n; i++)
            if(id[pre[i]] == id[i]) //如果当前边的起点和终点在一个强连通分量,说明该边在环里
                res += d[pre[i]][i];

        //缩点
        //将备份数组清空
        for(int i = 1; i <= cnt; i++)
            for(int j = 1; j <= cnt; j++)
                bd[i][j] = INF;

        //用备份数组记录缩点后图中每个点直接的边权
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                //如果两个点之间有边,且不在一个强连通分量中,说明这是一条缩点后仍存在的边
                if(d[i][j] < INF && id[i] != id[j])
                {
                    int a = id[i], b = id[j];
                    //如果 j 和 j 的前驱点在同一个强连通分量中,说明该边的终点 j 在环里
                    if(id[pre[j]] == id[j]) bd[a][b] = min(bd[a][b], d[i][j] - d[pre[j]][j]); //更新边权
                    else bd[a][b] = min(bd[a][b], d[i][j]); //否则不需要更新直接照抄
                }

        //将新图代替原图
        n = cnt;
        memcpy(d, bd, sizeof d);
    }

    return res;
}

int main()
{
    while(scanf("%d%d", &n, &m) != -1)
    {
        for(int i = 1; i <= n; i++) scanf("%lf%lf", &a[i].first, &a[i].second);

        memset(g, 0, sizeof g); //初始化
        while(m--)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            if(a != b && b != 1) g[a][b] = true; //边不能存在自环,且回到 1 的边不用存
        }

        if(!check()) puts("poor snoopy"); //如果图不连通,说明无解
        else printf("%.2lf\n", work()); //否则说明有解,输出答案
    }
    return 0;
}


活动打卡代码 AcWing 2417. 指挥网络

#include <iostream>
#include <cstring>
#include <cmath>

using namespace std;

typedef pair<double, double> PDD;

const int N = 110;
const double INF = 1e8;

int n, m;
PDD a[N]; //记录所有点的坐标
bool g[N][N]; //邻接矩阵
double d[N][N], bd[N][N]; //记录每两个点之间的距离、备份
int pre[N]; //记录每个点选择的前驱点
int dfn[N], low[N], timestamp; //tarjan 算法的数组
int stk[N], top; //栈
bool in_stk[N]; //记录每个点是否在栈中
int id[N], cnt; //记录每个点所在的强连通分量编号
bool st[N]; //记录每个点能否从 1 号点搜索到

void dfs(int u) //从 u 节点往下搜索所有点
{
    st[u] = true;

    for(int i = 1; i <= n; i++)
        if(g[u][i] && !st[i])
            dfs(i);
}

bool check() //判断整个图是否具有连通性
{
    memset(st, 0, sizeof st); //初始化
    dfs(1); //从 1 号点开始搜索所有点

    for(int i = 1; i <= n; i++)
        if(!st[i])
            return false; //如果某个点搜不到,说明图不连通
    return true; //否则说明连通
}

double get_dist(int i, int j) //计算两个点之间的距离
{
    double x = a[i].first - a[j].first;
    double y = a[i].second - a[j].second;
    return sqrt(x * x + y * y);
}

void tarjan(int u) //tarjan 算法缩点
{
    dfn[u] = low[u] = ++timestamp;
    stk[++top] = u, in_stk[u] = true;

    //由于每个点只有一条入边,不需要循环
    int j = pre[u];
    if(!dfn[j])
    {
        tarjan(j);
        low[u] = min(low[u], low[j]);
    }
    else if(in_stk[j]) low[u] = min(low[u], dfn[j]);

    //找到一个环
    if(dfn[u] == low[u])
    {
        int y;
        cnt++;
        do
        {
            y = stk[top--];
            in_stk[y] = false;
            id[y] = cnt;
        } while(y != u);
    }
}

double work() //计算答案
{
    double res = 0; //记录答案

    //计算每两个点之间的距离
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            if(g[i][j]) d[i][j] = get_dist(i, j); //存在边,计算距离
            else d[i][j] = INF; //不存在边,距离为 INF

    //朱刘算法
    while(true)
    {
        //对于每个点,选择它所有入边中最小的一条边
        for(int i = 1; i <= n; i++)
        {
            pre[i] = i;
            for(int j = 1; j <= n; j++)
                if(d[pre[i]][i] > d[j][i]) //如果边更小,更换
                    pre[i] = j;
        }

        //初始化
        memset(dfn, 0, sizeof dfn);
        timestamp = top = cnt = 0;

        //tarjan 算法求环
        for(int i = 1; i <= n; i++)
            if(!dfn[i])
                tarjan(i);

        if(cnt == n) //如果缩点后还是 n 个点,说明不存在环
        {
            for(int i = 2; i <= n; i++) res += d[pre[i]][i]; //累加所有选中的边的权值
            break;
        }

        //否则说明有环,将环内所有边的权值累加到答案中
        for(int i = 2; i <= n; i++)
            if(id[pre[i]] == id[i]) //如果当前边的起点和终点在一个强连通分量,说明该边在环里
                res += d[pre[i]][i];

        //缩点
        //将备份数组清空
        for(int i = 1; i <= cnt; i++)
            for(int j = 1; j <= cnt; j++)
                bd[i][j] = INF;

        //用备份数组记录缩点后图中每个点直接的边权
        for(int i = 1; i <= n; i++)
            for(int j = 1; j <= n; j++)
                //如果两个点之间有边,且不在一个强连通分量中,说明这是一条缩点后仍存在的边
                if(d[i][j] < INF && id[i] != id[j])
                {
                    int a = id[i], b = id[j];
                    //如果 j 和 j 的前驱点在同一个强连通分量中,说明该边的终点 j 在环里
                    if(id[pre[j]] == id[j]) bd[a][b] = min(bd[a][b], d[i][j] - d[pre[j]][j]); //更新边权
                    else bd[a][b] = min(bd[a][b], d[i][j]); //否则不需要更新直接照抄
                }

        //将新图代替原图
        n = cnt;
        memcpy(d, bd, sizeof d);
    }

    return res;
}

int main()
{
    while(scanf("%d%d", &n, &m) != -1)
    {
        for(int i = 1; i <= n; i++) scanf("%lf%lf", &a[i].first, &a[i].second);

        memset(g, 0, sizeof g); //初始化
        while(m--)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            if(a != b && b != 1) g[a][b] = true; //边不能存在自环,且回到 1 的边不用存
        }

        if(!check()) puts("poor snoopy"); //如果图不连通,说明无解
        else printf("%.2lf\n", work()); //否则说明有解,输出答案
    }
    return 0;
}



最小树形图(朱刘算法)的相关概念

树形图的定义:

  1. 以某一个点为根的有向树,被称为 树形图

  2. 一个有向图,满足无环且每个点的入度为 $1$ (除了根节点),被称为 树形图

最小树形图: 对于所有树形图中,找到一个总权值和最小的树形图,被称为 最小树形图

最小树形图问题本质上其实就是有向图上的最小生成树问题。Prim 算法和 Kruskal 算法可以解决无向图上的最小生成树问题。朱刘算法可以解决有向图上的最小生成树问题。


朱刘算法

朱刘算法是一个迭代算法,每一次迭代:
1. 除了根节点,对于每个点,找一下这个点的入边中权值最小的边
2. 判断选出的边中是否存在环
$(1)$ 无环,算法结束
$(2)$ 有环,进入步骤 $3$
3. 将所有环缩点,得到新图 $G’$,对于每条边:
$(1)$ 环内部的边,删去
$(2)$ 边的终点 $u$ 在环内,该边的权值变成原权值减去 $u$ 在环内的边的权值,即 $w - w_{环}$
$(3)$ 其他边,不变

算法结束后,之前每一次迭代选出的所有边的总权值之和就是答案。


证明朱刘算法

如果第一次选出的边中不存在环,就意味着当前选出的边满足两个条件,无环且每个点都有一个入边,说明我们选出的是一个树形图,由于每个点选出的边都是所有入边里面权值最小的边,所以一定不可能存在其他方案使得我们选择的边权和更小。

如果有环,那么为什么算法还是对的呢?

假设原图是 $G$,而缩完点且更新完边权之后的图是 $G’$。

我们考虑 $G$ 中任意一个环,由于最终图中一定不能存在环,所以这个环一定存在两个性质,第一点是至少需要去掉一条边,第二点是必然存在一个最优解只去一条边。

假设我们现在任意去掉一条边 $a$,那么必然会选一条新边 $b$ 连向 $a$ 的终点,此时如果我们在任意去掉另外一条边 $c$,那么必然会再选一条新边 $d$ 连向 $c$ 的终点。此时由于 $c$ 一定小于等于 $d$,并且由于去掉了 $a$,选上 $c$ 并不能让图中存在环且权值会变小,因此我们一定可以把 $d$ 换回 $c$。按照这个原理,任意给我们一个最优解,如果最优解中去掉的边数大于 $1$,那么我们必然可以从新加的边去掉,换回环上的边,这样它仍然满足是一个树形图,但是总边权和不会变大。由此得出对于任意一个环,必然存在一个最优解只去一条边。

有了以上两个性质,我们可以进行证明。

假设图 $G$ 中所有环里面只去掉环上一条边的树形图的集合放在左边,将 $G’$ 里面所有树形图的集合放在右边。

对于左边集合中的图的任何一个环,我们只去掉一条边,然后连上一条新边,由于环已经被我们缩点,那么新边就会连向缩点后的新点,对于新点而言,入边就是唯一的,所以去掉一条边后图中无环且每个点的入度为 $1$,所以去掉一条边后会构成一个树形图,说明左边集合的任意一个图,我们都可以转化成右边集合的一个树形图。

反过来,对于右边集合中任意一个树形图,我们找到一个不是根节点的缩点后的点,那么这个点必然存在一个入边,且这个入边必然是原图里的某一条边,且它一定连向缩点后这个点内部的某一个点,我们将这个点对应的内部的边去掉,将这条原图中的边加上。这样可以发现,任给我们一个右边集合的树形图,我们都可以转化成左边集合的一个满足两个性质的树形图。

因此两个集合是相互对应的。

然后看一下数量关系,可以发现左边集合加上了一条环外边 $w$,去掉了一条环内边 $w’$,因此整个操作等于是加上了 $w-w’$,而右边集合中我们定义每条边就是 $w-w’$,所以两个集合在数量关系上也是完全一样的。

综上所述,我们想求左边集合的最小树形图只需要求右边集合的最小树形图就行了,因此每次图中有环进行的处理是正确的。

每次迭代最多去掉一个点,最多迭代 $n$ 次,每次迭代内部是时间复杂度是 $O(m)$,因此整个算法时间复杂度是 $O(nm)$




月之谜

解题思路

求一个区间内满足某种限制条件的数有多少个,是一个经典的数位 dp 问题。

设 $f[i][j][k][l]$ 表示由 $i$ 位数字构成、各位数字之和是 $j$、对 $k$ 取模余数是 $l$ 的数有多少个。

在计算 $f$ 时,允许前导 $0$ 的存在,枚举第 $i$ 位的数字 $p$,得到状态转移方程:

$$f[i][j][k][l] = \sum_{p=0}^{9} f[i - 1][j - p][k][(l - p * 10^{i-1}) \% k]$$

闭区间 $[L, R]$ 种月之数的个数,等于 $[1, R]$ 种月之数的个数减去 $[1, L-1]$ 种月之数的个数。接下来以 $[1,R]$ 进行说明。

采取 “试填法” 的思想,从高位到低位给每一位填数,只要填了一个比上限 $R$ 小的数位,那么后边的数位无论是多少,整个数值都不会超过 $R$,此时就可以立即把 dp 预处理出的结果累加到答案中。只有在每一位上始终填写与上限 $R$ 相同的数字时,才需要继续向后扫描,所以最终的计算量是数值的 “位数” 级别的,非常小。

我们枚举最终的各位数字之和 $sum$,然后从左到右扫描每个数位,设当前正在处理第 $i$ 位(最高位为第 $N$ 位,最低位为第 $1$ 位),当前已经填写的数字之和是 $t$,当前数值对 $sum$ 取模余数是 $q$,我们从小到大枚举第 $i$ 位要填的数字 $p$。

  1. 若 $p$ 小于上限 $R$ 在第 $i$ 位上的数字,则后边 $i - 1$ 位可以随便填,因为最终的数值能被 $sum$ 整除,所以第 $1 \sim i$ 位构成的数值对 $sum$ 取模的余数应该是 $sum - q$,因此答案直接累加 $f[i-1][sum-t-p][sum][(sum-q-p * 10^{i-1}) \% sum]$
  2. 否则,令 $t = t + p, q = q + p * 10^{i-1} \% sum$,开始处理第 $i-1$ 位

$[1, L-1]$ 同理。

dp 的计算量约为 $10*9^7$,每组数据查询的计算量为 $90*10*9$。


C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

int f[11][83][83][83]; //设 f[i][j][k][l] 表示由 i 位数字构成、各位数字之和是 j、对 k 取模余数是 l 的数有多少个
int pow10[11][83]; //设 pow10[i][k] 表示 10^i % k

int mod(int x, int mod) //求正余数
{
    return (x % mod + mod) % mod;
}

void init() //预处理 pow10, f
{
    for(int k = 1; k <= 82; k++)
    {
        //预处理 pow10
        pow10[0][k] = 1 % k;
        for(int i = 1; i <= 10; i++) pow10[i][k] = pow10[i - 1][k] * 10 % k;

        //预处理 f
        f[0][0][k][0] = 1;
        for(int i = 1; i <= 10; i++)
            for(int j = 0; j <= 82; j++)
                for(int l = 0; l < k; l++)
                    for(int p = 0; p <= 9; p++)
                    {
                        if(j - p < 0) break; //如果不合法直接结束当前循环
                        f[i][j][k][l] += f[i - 1][j - p][k][mod(l - p * pow10[i - 1][k], k)]; //状态转移方程
                    }
    }
}

int count(int x) //统计 1 ~ x 中的月之数个数
{
    int a[11], n = 0; //存储 x 的每一位
    while(x)
    {
        a[++n] = x % 10;
        x /= 10;
    }

    int res = 0; //记录 1 ~ x 中的月之数个数
    for(int sum = 1; sum <= 82; sum++) //枚举各位数字之和
    {
        int t = 0; //记录 x[n ~ i - 1] 的各位数字之和
        int q = 0; //记录 x[n ~ i - 1] 的数值对 sum 取模的余数
        for(int i = n; i >= 1; i--) //从高位到低位枚举
        {
            for(int p = 0; p < a[i]; p++) //统计第 n ~ i - 1 位与 x 相等,第 i 位小于 x 的月之数个数(即统计除 x 以外的月之数个数)
            {
                if(sum - t - p < 0) break; //如果不合法直接结束当前循环
                res += f[i - 1][sum - t - p][sum][mod(sum - q - p * pow10[i - 1][sum], sum)];
            }
            t += a[i];
            q = (q + a[i] * pow10[i - 1][sum]) % sum;
        }
        if(t == sum && q == 0) res++; //如果 x 各位数字之和为 sum,且能被 sum 整除,说明 x 也是月之数,res + 1
    }
    return res;
}

int main()
{
    init(); //预处理 pow10, f

    int l, r;
    while(scanf("%d%d", &l, &r) != -1) printf("%d\n", count(r) - count(l - 1)); //前缀和求区间

    return 0;
}