[NOIP2015 提高组] 运输计划

题目背景

公元 $2044$ 年，人类进入了宇宙纪元。

题目描述

公元 $2044$ 年，人类进入了宇宙纪元。

L 国有 $n$ 个星球，还有 $n-1$ 条双向航道，每条航道建立在两个星球之间，这 $n-1$ 条航道连通了 L 国的所有星球。

小 P 掌管一家物流公司， 该公司有很多个运输计划，每个运输计划形如：有一艘物流飞船需要从 $u_i$ 号星球沿最快的宇航路径飞行到 $v_i$ 号星球去。显然，飞船驶过一条航道是需要时间的，对于航道 $j$，任意飞船驶过它所花费的时间为 $t_j$，并且任意两艘飞船之间不会产生任何干扰。

为了鼓励科技创新， L 国国王同意小 P 的物流公司参与 L 国的航道建设，即允许小 P 把某一条航道改造成虫洞，飞船驶过虫洞不消耗时间。

在虫洞的建设完成前小 P 的物流公司就预接了 $m$ 个运输计划。在虫洞建设完成后，这 $m$ 个运输计划会同时开始，所有飞船一起出发。当这 $m$ 个运输计划都完成时，小 P 的物流公司的阶段性工作就完成了。

如果小 P 可以自由选择将哪一条航道改造成虫洞， 试求出小 P 的物流公司完成阶段性工作所需要的最短时间是多少？

输入格式

第一行包括两个正整数 $n, m$，表示 L 国中星球的数量及小 P 公司预接的运输计划的数量，星球从 $1$ 到 $n$ 编号。

接下来 $n-1$ 行描述航道的建设情况，其中第 $i$ 行包含三个整数 $a_i, b_i$ 和 $t_i$，表示第 $i$ 条双向航道修建在 $a_i$ 与 $b_i$ 两个星球之间，任意飞船驶过它所花费的时间为 $t_i$。

数据保证

接下来 $m$ 行描述运输计划的情况，其中第 $j$ 行包含两个正整数 $u_j$ 和 $v_j$，表示第 $j$ 个运输计划是从 $u_j$ 号星球飞往 $v_j$号星球。

输出格式

一个整数，表示小 P 的物流公司完成阶段性工作所需要的最短时间。

样例 #1

样例输入 #1

6 3 
1 2 3 
1 6 4 
3 1 7 
4 3 6 
3 5 5 
3 6 
2 5 
4 5

样例输出 #1

11

提示

所有测试数据的范围和特点如下表所示

请注意常数因子带来的程序效率上的影响。

对于 $100\%$ 的数据，保证：$1 \leq a_i,b_i \leq n$，$0 \leq t_i \leq 1000$，$1 \leq u_i,v_i \leq n$。

算法1

(树上差分+二分答案) $O(m \log n)$

由于答案有单调性，考虑二分$mid$的时间可以运输完吗
判定:
对于不改动时间>mid的路径，将路径上的边加一次
对于每条边，若每条不合法的路径都加了一次，那么如果不合法的最长路径-该边的长<=mid，判定成功
否则，判定失败

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 300010, M = N * 2, K = 20;

inline int read()
{
    int s = 0, w = 1;
    char c = getchar();
    for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
    for (; isdigit(c); c = getchar()) s = (s << 3) + (s << 1) + (c ^ 48);
    return s * w;
}

typedef long long LL;

struct Edge
{
    int a, b, w;
}edge[N], query[N];

int n, m, p[N];
int h[N], e[M], w[M], ne[M], idx;
int d[N];
LL dist[N], res, q_dist[N];
int fa[N][K];
int f[N];
int q[N];

void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

void bfs()
{
    int hh = 0, tt = 0;
    q[0] = 1;
    d[1] = 1;

    while (hh <= tt)
    {
        int t = q[hh ++ ];
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];

            if (d[j]) continue;

            d[j] = d[t] + 1;
            dist[j] = dist[t] + w[i];

            fa[j][0] = t;
            for (int k = 1; k <= 19; k ++ ) fa[j][k] = fa[fa[j][k - 1]][k - 1];

            q[ ++ tt] = j;
        }
    } 
}

int lca(int a, int b)
{
    if (d[a] < d[b]) swap(a, b);

    for (int i = 19; i >= 0; i -- )
        if (d[fa[a][i]] >= d[b])
            a = fa[a][i];
    if (a == b) return a;

    for (int i = 19; i >= 0; i -- )
        if (fa[a][i] != fa[b][i])
            a = fa[a][i], b = fa[b][i];
    return fa[a][0];
}

void dfs(int u, int fa)
{
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (j == fa) continue;

        dfs(j, u);

        f[u] += f[j];
    }
}

LL get_dist(int a, int b) //树上两点距离
{
    return dist[a] + dist[b] - 2 * dist[lca(a, b)];
}

bool check(LL mid)
{
    memset(f, 0, sizeof f);

    int cnt = 0;
    LL maxd = 0;
    for (int i = 1; i <= m; i ++ )
    {
        int a = query[i].a, b = query[i].b;
        if (q_dist[i] > mid)
        {
            cnt ++ ;
            f[a] ++ , f[b] ++ , f[p[i]] -= 2; //树上差分
            maxd = max(maxd, q_dist[i]);
        }
    }

    dfs(1, -1);

    for (int i = 1; i < n; i ++ )
    {
        int a = edge[i].a, b = edge[i].b;
        if (d[a] < d[b]) swap(a, b);

        if (f[a] == cnt && maxd - edge[i].w <= mid) return true;
    }

    return false;
}

int main()
{
    memset(h, -1, sizeof h);
    n = read(), m = read();

    for (int i = 1; i < n; i ++ )
    {
        int a, b, c;
        a = read(), b = read(), c = read();

        add(a, b, c), add(b, a, c);
        edge[i] = {a, b, c};
    }

    bfs(); //倍增LCA

    for (int i = 1; i <= m; i ++ )
    {
        int a, b;
        a = read(), b = read();

        query[i] = {a, b};
        q_dist[i] = get_dist(a, b);
        p[i] = lca(a, b);
        //printf("%lld\n", get_dist(a, b));
    }

    LL l = 0, r = 1e18;
    while (l < r) //二分答案
    {
        LL mid = l + r >> 1;

        if (check(mid)) r = mid;
        else l = mid + 1;
    }

    printf("%lld\n", r);

    return 0;
}

求赞QAQ

[NOIP2014 提高组] 联合权值

题目描述

无向连通图 $G$ 有 $n$ 个点，$n-1$ 条边。点从 $1$ 到 $n$ 依次编号,编号为 $i$ 的点的权值为 $W_i$，每条边的长度均为 $1$。图上两点 $(u, v)$ 的距离定义为 $u$ 点到 $v$ 点的最短距离。对于图 $G$ 上的点对 $(u, v)$，若它们的距离为 $2$，则它们之间会产生$W_v \times W_u$ 的联合权值。

请问图 $G$ 上所有可产生联合权值的有序点对中，联合权值最大的是多少？所有联合权值之和是多少？

输入格式

第一行包含 $1$ 个整数 $n$。

接下来 $n-1$ 行,每行包含 $2$ 个用空格隔开的正整数 $u,v$，表示编号为 $u$ 和编号为 $v$ 的点之间有边相连。

最后 $1$ 行,包含 $n$ 个正整数，每两个正整数之间用一个空格隔开，其中第 $i$ 个整数表示图 $G$ 上编号为 $i$ 的点的权值为 $W_i$。

输出格式

输出共 $1$ 行,包含 $2$ 个整数，之间用一个空格隔开,依次为图 $G$ 上联合权值的最大值和所有联合权值之和。由于所有联合权值之和可能很大，输出它时要对$10007$取余。

样例 #1

样例输入 #1

5  
1 2  
2 3
3 4  
4 5  
1 5 2 3 10

样例输出 #1

20 74

提示

本例输入的图如上所示，距离为2 的有序点对有$( 1,3)$ 、$( 2,4)$ 、$( 3,1)$ 、$( 3,5) $、$( 4,2)$ 、$( 5,3) $。

其联合权值分别为2 、15、2 、20、15、20。其中最大的是20，总和为74。

【数据说明】

对于30%的数据，$1 < n \leq 100$；

对于60%的数据，$1 < n \leq 2000$；

对于100%的数据，$1 < n \leq 200000, 0 < W_i \leq 10000$。

保证一定存在可产生联合权值的有序点对。

算法1

(树的遍历) $O(n)$

首先，距离为2的点对有两种

• 该结点和他父亲的父亲结点，即该节点和他的爷爷
• 该结点和他的兄弟结点

对于第一种情况，预处理出每个结点的爷爷结点,直接计算即可

对于第二种情况，预处理出除了该节点的父亲的儿子的最大值次大值和总权值，最后计算即可

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 2000010, mod = 10007;

typedef long long LL;

int n, w[N];
LL tot[N], maxx[N][2];
int h[N], e[N * 2], ne[N * 2], idx;
int d[N], fa[N][2];
int q[N];

void add(int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}

void bfs()
{
    int hh = 0, tt = 0;
    q[0] = 1;
    d[1] = 1;

    while (hh <= tt)
    {
        int t = q[hh ++ ];

        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];

            if (d[j]) continue;

            tot[t] += w[j]; //总权值
            if (w[j] > maxx[t][0]) //最大值和次大值
            {
                maxx[t][1] = maxx[t][0];
                maxx[t][0] = w[j];
            } else if (w[j] > maxx[t][1]) maxx[t][1] = w[j];

            d[j] = d[t] + 1;
            fa[j][0] = t, fa[j][1] = fa[t][0]; //父亲结点和爷爷结点

            q[ ++ tt] = j;
        }
    }
}

int main()
{
    memset(h, -1, sizeof h);
    scanf("%d", &n);

    for (int i = 1; i < n; i ++ )
    {
        int a, b;
        scanf("%d%d", &a, &b);

        add(a, b), add(b, a);
    }
    for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]);

    bfs();

    LL res = 0; 
    for (int i = 1; i <= n; i ++ ) //第一种情况
        if (fa[i][1])
            res = max(res, (LL)w[i] * w[fa[i][1]]);
    for (int i = 1; i <= n; i ++ ) //第二种情况
        if (fa[i][0])
        {
            if (w[i] == maxx[fa[i][0]][0]) res = max(res, w[i] * maxx[fa[i][0]][1]); //该节点是最大值，改用次大值
            else res = max(res, w[i] * maxx[fa[i][0]][0]);
        }

    printf("%lld ", res);

    res = 0;
    for (int i = 1; i <= n; i ++ )
        if (fa[i][1])
            res = (res + (LL)w[i] * w[fa[i][1]] % mod) % mod;
    res = res * 2 % mod;
    for (int i = 1; i <= n; i ++ )
        if (fa[i][0])
            res = (res + (LL)w[i] * (tot[fa[i][0]] - w[i]) % mod) % mod;
    printf("%lld\n", res);

    return 0;
}

class Solution {
public:
    void sortColors(vector<int>& nums) {
        vector<int> count(3, 0);

        for (int i = 0; i < nums.size(); i ++ ) count[nums[i]] ++ ;

        for (int i = 0, t = 0; i < 3; i ++ )
            for (int j = 0; j < count[i]; j ++ )
                nums[t ++ ] = i;
    }
};

class Solution {
public:
    string simplifyPath(string path) {
        string res, name;
        if (path.back() != '/') path += '/';

        for (auto c : path) {
            if (c != '/') name += c;
            else {
                if (name == "..") {
                    while (res.size() && res.back() != '/') res.pop_back();
                    if (res.size()) res.pop_back();
                }
                else if (name != "." && name != "") {
                    res += '/' + name;
                }
                name.clear();
            }
        }

        if (res.empty()) res = "/";
        return res;
    }
};

class Solution {
public:
    int minDistance(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        if (!n || !m) return n + m;

        vector<vector<int>> f(n + 1, vector<int>(m + 1));

        f[0][0] = 0;
        for (int i = 1; i <= n; i ++ ) f[i][0] = i;
        for (int j = 1; j <= m; j ++ ) f[0][j] = j;

        for (int i = 1; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ ) {
                f[i][j] = f[i - 1][j - 1] + 
                    (word1[i - 1] != word2[j - 1]);
                f[i][j] = min(f[i][j], f[i - 1][j] + 1);
                f[i][j] = min(f[i][j], f[i][j - 1] + 1);
            }
        return f[n][m];
    }
};

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size();
        int n = matrix[0].size();

        vector<bool> row(m), col(n);

        for (int i = 0; i < m; i ++ )
            for (int j = 0; j < n; j ++ )
                if (!matrix[i][j])
                    row[i] = col[j] = true;

        for (int i = 0; i < m; i ++ )
            for (int j = 0; j < n; j ++ )
                if (row[i] | col[j])
                    matrix[i][j] = 0;
    }
};

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if (matrix.empty() || matrix[0].empty()) return false;

        int n = matrix.size(), m = matrix[0].size();
        int l = 0, r = n * m - 1;

        while (l < r)
        {
            int mid = l + r >> 1;

            if (matrix[mid / m][mid % m] >= target) r = mid;
            else l = mid + 1;
        }

        return matrix[r / m][r % m] == target;
    }
};

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> hash;
        int cnt = 0;

        for (auto c : t)
        {
            if (!hash[c]) cnt ++ ;
            hash[c] ++ ;
        }

        string res = "";
        for (int i = 0, j = 0, c = 0; i < s.size(); i ++ )
        {
            if (hash[s[i]] == 1) c ++ ;
            hash[s[i]] -- ;
            while (c == cnt && hash[s[j]] < 0) hash[s[j ++ ]] ++ ;

            if (c == cnt)
            {
                if (res.empty() || res.size() > i - j + 1) 
                    res = s.substr(j, i - j + 1);
            }
        }

        return res;
    }
};

class Solution {
public:
    vector<vector<int>> res;
    vector<int> path;
    void dfs(int u, int last, int& n, int& k)
    {
        if (u == k) 
        {
            res.push_back(path);
            return ;
        }

        for (int i = last + 1; i <= n; i ++ )
        {
            path.push_back(i);
            dfs(u + 1, i, n, k);
            path.pop_back();
        }
    }

    vector<vector<int>> combine(int n, int k) {

        dfs(0, 0, n, k);
        return res;
    }
};