5.3 最长隧道

发表于 | 更新于 | 分类于 | 阅读次数：

实验任务

\(C\)国有\(N\)个城市，由\(N-1\)条道路连接，保证可以从一个城市到达其他任意一个城市。国王挑选出\(2\times k\)个重要的城市，将其分为\(k\)组，在每组的两个城市间，沿着道路修筑隧道，来为战争做准备。假设所有的道路长度为1，现在帮助国王分组，使得按照该分组方案进行修筑隧道后，所有隧道的长度之和最大（两不同组若在同一段道路上修建隧道，算作两条）。

数据输入

输入第一行包括两个整数\(N\)和\(K\ (2\leq N\leq 20000,1\leq K\leq n/2)\)，为城市的总个数和重要城市的组数。第二行包括\(2\times K\) 个不同的整数，表示重要城市的编号。接下来\(N-1\)行，每行包括两个整数\(X\)和\(Y\ (1\leq X,Y\leq N)\)，表示\(X\)和\(Y\)两个城市之间有一条道路。

数据输出

输出整数\(K\)，表示隧道的最大长度和。

输入示例 输出示例
7 2
4 5 6 7
1 2
1 3
2 4
2 5
3 6
3 7		 8

源代码

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
#include <stdio.h>
#include <vector>
using namespace std;
#define maxn 20005

inline int min(int a, int b){ return a < b ? a : b; }

class Node{
public:
    int pair;
    vector<int> son;
    Node() :pair(0){}
};

class Tree{
public:
    int k;
    Node node[maxn];
    void in()
    {
        int n, i, u, v;
        scanf("%d%d", &n, &k);
        k <<= 1;
        for (i = 0; i < k; ++i){
            scanf("%d", &u);
            tree.node[u].pair = 1;
        }
        for (i = 1; i < n; ++i){
            scanf("%d%d", &u, &v);
            node[u].son.push_back(v);
            node[v].son.push_back(u);
        }
    }
    int dfs(int root, int parent){
        int ret = 0;
        if (node[root].son.size() == 1)return 0;
        for (int i = 0; i < node[root].son.size(); ++i){
            int son = node[root].son[i];
            if (son == parent)continue;
            ret += dfs(son, root);
            ret += min(node[son].pair, k - node[son].pair);
            node[root].pair += node[son].pair;
        }
        return ret;
    }
}tree;

int main(){
    tree.in();
    printf("%d\n", tree.dfs(1, 0));
}

设计思路与复杂度分析

问题转化：与每条隧道最长等价的问题是，每一条边有尽可能多的隧道通过。

最小配对原则：假设一条边将一棵树分成了两个部分，若左边有v个要挑选的城市，则右边必有\((2\times K-v)\)个要挑选城市。要使该边通过的隧道数尽可能多，则重要城市少的部分的所有重要城市必须通过该边与重要城市多的部分连接，因此该边必有\(min(2\times k-v,v)\)条隧道通过。

实现上使用\(dfs\)即可知道每一条边树形结构下方的重要城市数，复杂度为：\(O(n)\)。

0%