最小生成树

Kruskal算法：（稀疏图）

按照边权排序，用并查集维护

未连接的：连上

已经连接的：忽略

时间复杂度是O(mlogn)

Prim算法：（稠密图 O(n^2)）

邻阶矩阵存储， d[i]表示i这个未选节点到已选集合的距离

每次找到最小距离（未选点到已选集合）

走廊泼水节

题目链接

走廊泼水节

描述：给一个树，求一个完全图所加边的权值之和最小值，并且这个图的最小生成树任然是这个树。

题解思路

就是在求最小生成树的时候，用Kruskal算法, 当两个集合需要合并的时候，这两个集合连线是最小的，两个集合其他点连线的权值就是这个两个集合连线最小值+1

题目代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;
const int N = 6010;
struct edge {
    int x, y, z;
    
} a[N];
int fa[N], Size[N];
int n;

bool operator <(const edge& a, const edge& b) {
    return a.z < b.z;
}

int get(int x) {
    if (x == fa[x]) return x;
    return fa[x] = get(fa[x]);
}

int main() {
    int T; cin >> T;
    while (T--) {
        cin >> n;
        for (int i = 1; i <= n - 1; i++)
            scanf("%d%d%d", &a[i].x, &a[i].y, &a[i].z);
        sort(a+1, a+n);
        for (int i = 1; i <= n; i++) fa[i] = i, Size[i] = 1;
        int ans = 0;
        for (int i = 1; i <= n - 1; i++) {
            int x = get(a[i].x);
            int y = get(a[i].y);
            if (x != y) {
                fa[y] = x;
                ans += (a[i].z + 1) * (Size[x] * Size[y] - 1);  //其他未连接的边权值之和
                Size[x] += Size[y]; 
            }
        }
        cout << ans << endl;
    }
}

野餐规划

题目链接

野餐规划

描述：1号节点有限制，求生成树的最小边权之和

题解思路

思路一：删除1号节点的一条边，再加一条边，使得代价最小（贪心思想），枚举所有可以删除的边，在枚举所有可添加的边，使得删除添加的代价最小。

思路二：加边，然后去边

题目代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include<bits/stdc++.h>

using namespace std;

int n, m, s, deg, ans;  //节点个数， 

const int N = 25;
int a[N][N], d[N], conn[N];
bool v[N];
int tree[N][N];

//用一个map做映射
void read() {
    map<string, int> h;
    cin >> m;
    h["Park"] = 1; n = 1;
    memset(a, 0x3f, sizeof(a));         //原图对应的邻接矩阵
    for (int i = 1; i <= m; i++) {
        int x, y, z;
        char sx[12], sy[12];
        scanf("%s%s%d", sx, sy, &z);
        if (!h[sx]) h[sx] = ++n; //节点个数+1
        if (!h[sy]) h[sy] = ++n;
        x = h[sx], y = h[sy];
        a[x][y] = min(a[x][y], z);      //原图邻接矩阵存储
        a[y][x] = min(a[y][x], z);
    }
    cin >> s;
}

//原图的最小生成树
void prim() {
    memset(d, 0x3f, sizeof(d));
    memset(v, 0, sizeof(v));
    d[1] = 0;
    for (int i = 1; i < n; i++) {
        int x = 0;
        for (int j = 1; j <= n; j++)
            if (!v[j] && (x == 0 || d[j] < d[x])) x = j;
        v[x] = true;    
        for (int y = 1; y <= n; y++)
            if (!v[y] && d[y] > a[x][y])
                d[y] = a[x][y], conn[y] = x;        //连接y的是x，即是(x -> y)
    }
    memset(tree, 0x3f, sizeof(tree));               //最小生成树对应的邻接矩阵
    for (int i = 2; i <= n; i++) {
        ans += d[i];
        if (conn[i] == 1) deg++;                    //从1节点到其他节点个数+1
        tree[conn[i]][i] = tree[i][conn[i]] = d[i]; //最小生成树对应的邻接矩阵
    }
}

//当前连通块的所有节点都标记一下
void dfs(int x) { 
    v[x] = true;
    for (int y = 1; y <= n; y++)
        if (tree[x][y] != 0x3f3f3f3f && !v[y]) dfs(y);
}

int find_min(int& x, int& y) {              //考虑原图中加入哪条边把v=true和v=false的两个块连起来
    int min_edge = 1 << 30;
    for (int i = 2; i <= n; i++) 
        if (v[i])               //是true的点
            for (int j = 2; j <= n; j++) 
                if (!v[j])      //是false的点
                    if (a[i][j] < min_edge) min_edge = a[i][j], x = i, y = j;   //找到最小方案
    return min_edge;
}

void solve() {
    int min_val = 1 << 30, mini, minx, miny;
    for (int i = 2; i <= n; i++) {              //枚举从1出发的树边(1, i)，看删去哪一条
        if (tree[1][i] == 0x3f3f3f3f) continue; //如果不存在直接跳过
        memset(v, 0, sizeof(v));                
        v[1] = true;                            //考虑的是1之外的两个连通块，1不能用
        dfs(i);                                 //标记当前连通块所有节点
        int x, y;
        int add_edge = find_min(x, y);          //加入(x,y)，找到被标记的连通块，与false连通块连接的最小边
        if (add_edge < 0x3f3f3f3f && add_edge - tree[1][i] < min_val) {
            min_val = add_edge - tree[1][i];    //求出最小代价
            mini = i, minx = x, miny = y;       //删的点，加的边
        }
    }
    ans += min_val;                             //代价加起来
    tree[1][mini] = tree[mini][1] = 0x3f3f3f3f;             //删除这条边
    tree[minx][miny] = tree[miny][minx] = a[minx][miny];    //添加一条边
}

int main() {
    read();
    prim();
    while (deg > s) {
        solve();
        deg--;
    }
    printf("Total miles driven: %d\n", ans);
    
    return 0;
}

沙漠之王

题目链接

沙漠之王

题解思路

思路：

二分答案+最小生成树

根据题意求得是min(总成本/总长度)
转化 minx = 总成本/总长度
总成本 - minx (总长度) = 0
f(x) = 总成本 - minx (总长度)
函数单调递减，求解使f(x)=0的最小的x
要做的是满足任意一个生成树的f(x)>=0，得到最小的x
因为f(x)是个单调递减函数,随着x的增大而减少
对于任意一个生成树如果
f(x) > 0，l需要增大
f(x) < 0，l需要减小
所以最终可以用最小生成树 + 二分答案来求解

题目代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

#include <bits/stdc++.h>

using namespace std;

const int N = 1010;
const double eps = 1e-6;
int n, x[N], y[N], h[N];
double d[N];
bool v[N];

double calc(int a,int b){
    return sqrt((x[a]-x[b])*(x[a]-x[b]) + (y[a]-y[b])*(y[a]-y[b]));
}

bool check_prim(double mid){
    for(int i = 0; i < N; i++)d[i] = 1e18, v[i] = 0;
    d[1] = 0;
    double res = 0;
    for(int i = 0; i < n; i++){
        int t = -1;
        for (int j = 1; j <= n; j++)
            if (!v[j] && (t == -1 || d[j] < d[t])) t = j;
        v[t] = true;
        res += d[t];    //确定这个点
        for(int j = 1; j <= n; j++){
            if(!v[j] && d[j] > fabs(h[j] - h[t]) - mid * calc(t, j) + eps)
                d[j] = fabs(h[j] - h[t]) - mid * calc(t, j);
        }
    }
    return res >= 0.0;
}

int main ()
{
    while(cin >> n && n){
        for(int i = 1; i <= n; i++){
            scanf("%d%d%d", &x[i], &y[i], &h[i]);
        }
        double l = 0, r = 10000001, ans;
        while((r - l) > eps){       //二分答案
            double mid = (l + r) / 2;
            if(check_prim(mid)) ans = mid, l = mid;
            else r = mid;
        }
        printf("%.3f\n", ans);
    }
}

黑暗城堡

题目链接

黑暗城堡

题解思路

最短路径树+最短路图

最短路径生成树，首先求出最短路（到达各个点的距离），然后根据prim的顺序求出每个点d[p] == d[x] + w(x , p)的边的数量，将这些数量相乘就是方案总数

题目代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
#define ll long long

using namespace std;

const int N = 1010;

int n, m, g[N][N], d[N];
bool v[N];

void dijkstra() {
    memset(d, 0x3f, sizeof d);
    d[1] = 0;
    for(int i = 1; i < n; i ++) {
        int t = -1;
        for(int j = 1; j <= n; j ++)
            if(!v[j] && (t == -1 || d[j] < d[t])) t = j;
        v[t] = true;
        for(int j = 1; j <= n; j ++)
            d[j] = min(d[j], d[t] + g[t][j]);
    }
}

int main() {
    memset(g, 0x3f, sizeof g);
    int mod = (1 << 31) - 1;
    cin >> n >> m;
    for(int i = 1; i <= m; i ++) {
        int x, y, z;
        scanf("%d%d%d", &x, &y, &z);
        g[x][y] = g[y][x] = min(g[x][y], z);
    }

    dijkstra(); //求最短路
    memset(v, 0, sizeof v);
    v[1] = true;
    ll ans = 1;
    for(int i = 1; i <= n; i ++){
        int x = 0, res = 0;
        for(int j = 2; j <= n; j ++)
            if(!v[j] && (x == 0 || d[x] > d[j])) x = j;       
        for(int j = 1; j <= n; j ++)
            if(v[j] && d[x] == g[j][x] + d[j]) res ++;  //相当于是与最短路路径相等的边的个数
        v[x] = true;
        ans = (ans * res) % mod;        //相等的边的个数相乘就是总的方案数
    }
    printf("%lld\n", ans);
    return 0;
}

朱-刘算法（最小树形图）

有向图，n - 1条有向边从root 出发，可以到达所有点，并且让边权之和最小

贪心每个点找最小入边，无环的话就是找到答案了；如果有环的话就是把环缩小为点，从环上出发的点 改为从新点出发，从点到环改为进入新点，改一下边权

image-20220322204552885

环缩点：

  1. 可以新建一个图，将环转化成一个点
  2. 可以每个环的各个点都用其中一个点作为代表

最小有向树形图
1 无环
2 每个点入度为1

朱刘算法
1 贪心的从每个点的所有入边中找一条权值最小的边
2 从选出的边中判断是否存在环
2.1 不存在环，结束，把所有边权值加上作为答案
2.2 存在环，进入第3步
3 将所有环缩点，构造新图G’，缩点前把所有边权值加上
3.1 环内的边 2->3 3->4 4->2
删去
3.2 终点在环内的边 1->4 1->2
权值 w’ = w - 终点入边权值
w[1->4]’ = w[1->4] - w[3->4] = 5 - 1 = 4
w[1->2]’ = w[1->2] - w[4->2] = 4 - 2 = 2
3.3 其他边 4->5
不变
每次缩一次点,点数最少-1,所以总共最多迭代n次算法结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cmath>

#define x first
#define y second

using namespace std;

typedef pair<double, double> PDD;//坐标 距离要开根号--double

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

int n, m;
PDD q[N];
bool g[N][N];//邻接矩阵 相邻
double d[N][N], bd[N][N];// 距离 备份数组
int pre[N], bpre[N];// 入边 备份数组
int dfn[N], low[N], ts, stk[N], top;// tarjan dfn序 low数组 时间戳 栈 栈顶
int id[N], cnt;//缩点后新图
bool st[N], ins[N];//判断从1号点能不能搜到所有点

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

bool check_con()
{
    memset(st, 0, sizeof st);
    dfs(1);
    for (int i = 1; i <= n; i ++ )
        if (!st[i])
            return false;
    return true;
}

double get_dist(int a, int b)
{
    double dx = q[a].x - q[b].x;
    double dy = q[a].y - q[b].y;
    return sqrt(dx * dx + dy * dy);
}

void tarjan(int u)
{
    dfn[u] = low[u] = ++ts;
    stk[++top]=u,ins[u]=true;

    int j = pre[u];
    if(!dfn[j])//没搜过 用low[j]更新low[u]
    {
        tarjan(j);
        low[u] = min(low[j],low[u]);
    }
    else if(ins[j])//在栈里 用dfn[j]更新low[u]
    {
        low[u] = min(low[u],dfn[j]);
    }
    if(low[u]==dfn[u])//比u低的j都dfs完了之后回到u发现u是最高的,开始把比u低的j出栈
    {
        int y;
        ++cnt;
        do
        {
            y=stk[top--],ins[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;

    while (true)
    {
        // 求所有入边的最小值
        for (int i = 1; i <= n; i ++ )
        {
            pre[i] = i;// 入边首先初始化为自己到自己的INF
            for (int j = 1; j <= n; j ++ )
                if (d[pre[i]][i] > d[j][i])
                    pre[i] = j;
        }
        // tarjan
        memset(dfn, 0, sizeof dfn);//dfs序
        ts = cnt = 0;//时间戳
        for (int i = 1; i <= n; i ++ )
            if (!dfn[i])//如果没被搜过就缩点
                tarjan(i);

        // 如果cnt==n ,没有环,把所有入边的权重求和即为答案
        if (cnt == 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])//判断规则: 边的起点和终点是否在一个scc内
                res += d[pre[i]][i];

        // 初始化bd数组 作为G'的距离
        for (int i = 1; i <= cnt; i ++ )
            for (int j = 1; j <= cnt; j ++ )
                bd[i][j] = INF;

        // 构建新图G'
        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];//起点a 终点b
                    // 如果终点在环内 则该入边 w' = w - w[环内入边权] = d[i][j] - d[pre[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更新为新的点数 , d更新为bd
        n = cnt;
        memcpy(d, bd, sizeof d);
    }

    return res;
}

int main()
{
    while (~scanf("%d%d", &n, &m))
    {
        for (int i = 1; i <= n; i ++ ) scanf("%lf%lf", &q[i].x, &q[i].y);

        memset(g, 0, sizeof g);
        while (m -- )
        {
            int a, b;
            scanf("%d%d", &a, &b);
            if (a != b && b != 1) g[a][b] = true;
        }

        if (!check_con()) puts("poor snoopy");//不连通 无解
        else printf("%.2lf\n", work());
    }

    return 0;
}

树的直径与最近公共祖先

定义：树中最远两个点之间的距离称为树的直径，连接这两点的路径称为树的最长链。

可以用树形dp来求

但是如果一个树的子节点比较多，那么就可能达到$n^2$的复杂度

可以在求最大深度d的时候去维护

1
2
3
4
5
6
7
8
9
10
void dp(int x){
    v[x] = 1;
    for(int i = head[x]; i != -1; i = next[i]){
        int y = ver[i];
        if(v[y]) continue;
        dp(y);
        ans = max(ans, d[x] + d[y] + edge[i]);
        d[x] = max(d[x], d[y] + edge[i]);
    }
}

两次bfs求树的直径(不能有负权边)

  1. 从任意一个点出发，到达最远点记为p点
  2. 从p点出发到达最远点，记为q点
  3. pq两点的距离就是树的直径

巡逻

题目链接

巡逻

题解思路

k == 1的时候就是求出树的最大直径，2 * (n - 1) - L1 + 1，就是最终答案

k == 2的时候需要将原来的最大直径公共边权值重新赋值为-1，继续求出直径，ans - L2 + 1, 当你第一次连接直径时, 原本要原路返回, 这条边会走两次, 你连接之后直走一次,第二次连接时, 这条边会由于你的连线非但没少走, 还会多走一边故, 贡献从 1 变为 -1.

题目代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <bits/stdc++.h>

using namespace std;

const int N = 100010;
int e[2 * N], ne[2 * N], w[2 * N], h[N], idx;
int n, k;
int d[N], pre[N], L2;

void add(int x, int y) {
    e[idx] = y, w[idx] = 1, ne[idx] = h[x], h[x] = idx++;
}

int bfs(int s) {
    memset(d, -1, sizeof(d));
    queue<int> q;
    q.push(s); 
    d[s] = 0;
    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int i = h[x]; ~i; i = ne[i]) {
            int y = e[i];
            if (d[y] == -1) {
                d[y] = d[x] + 1;
                pre[y] = i; // 记录前一个结点
                q.push(y);
            }
        }
    }
    int p = s;     
    
    //找到直径一端
    for(int i = 1; i <= n; i++)
        if(d[i] > d[p]) p = i;
    return p;
}

void update(int q, int p) {
    while (q != p) {
        w[pre[q]] = -1;
        w[pre[q] ^ 1] = -1; //反向图也修改一下权值
        q = e[pre[q] ^ 1];
    }
}

void dp(int x, int fa) {
    for (int i = h[x]; ~i; i = ne[i]) {
        int y = e[i];
        if (y == fa) continue;
        dp(y, x);
        L2 = max(L2, d[y] + w[i] + d[x]);
        d[x] = max(d[x], d[y] + w[i]);
    }
}

int main() {
    cin >> n >> k;
    memset(h, -1, sizeof h);
    for (int i = 1; i < n; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        add(x, y), add(y, x);
    }
    int p = bfs(1);
    int q = bfs(p);     //求树的直径两端
    int ans = 2 * (n - 1) - d[q] + 1;
    if (k == 2) {
        update(q, p);   //更新一下p到q的权值
        memset(d, 0, sizeof(d));
        dp(1, 0);       //树上dp求一下最大直径，（因为有权值为-1的边，不能用BFS或者DFS）
        ans = ans - L2 + 1;
    }
    cout << ans << endl;
}