【洛谷P2680】运输计划

这是新博客的第一篇博文2333,千里之行始于足下,希望有天这个博客的访问量能够大到逼着我换更好的服务器2333
这个题首先要求最大路径最短,可以考虑二分答案。然后我们考虑,假如说我们的答案是合法的,那么一定所有大于答案的路径上都有一个黑洞,不然这个答案就是不合法的,那么我们需要找这些路径所经过的共同的边,选取一个最长的边作为答案
这样我们直接一个个找肯定会超时,那么我们可以用差分来记录一条边被多少超过答案的路径所经过,在x~y这条路上,我们给x处、y处各+1,在x,y的lca上-2,最后处理前缀和,那么我们就可以求出哪些边可能成为虫洞了,最后选取最大的边
常数上个人倒是没感到太大鸭梨……当然可能是当年ccf老爷机的错,但是一些简单的卡常数比如手动读入这种最好还是写上,毕竟考前5分钟就写完,之后ctrl+c,ctrl+v就好

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#define ri register int

using namespace std;

const int mx = 1000000007;

typedef long long lo;

inline char gch()
{
    static char buf[100010], *h = buf, *t = buf;
    return h == t && ((t = (h = buf) + fread(buf, 1, 100000, stdin), t == h)) ? EOF : *h ++;
}

inline void re(int &x)
{
    x = 0;
    char a = gch(); bool b = 0;
    while(a < '0' || a > '9')
    {
        if(a == '-')
            b = 1;
        a = gch();
    }
    while(a >= '0' && a <= '9')
        x = (x << 3) + (x << 1) + a - '0', a = gch();
    if(b == 1)
        x *= -1;
}

int n, m, lx, ly, lz, ans, tot = -1, cnt, head[300030];

int ttp[300030], dis[300030], q[300030], de[300030], s[300030];

int fa[300030], sz[300030], son[300030], pos[300030], v1[300030], v2[300030];

struct in
{
    int to, ne, co;
}ter[600060];

struct es
{
    int x, y, c;
}ing[300030];

bool cmp(es a, es b)
{
    return a.c > b.c;
}

inline void build(int f, int l, int c)
{
    ter[++ tot] = (in){l, head[f], c}, head[f] = tot;
    ter[++ tot] = (in){f, head[l], c}, head[l] = tot;
}

void dfs1(int no)//两次dfs把树剖开 
{
    sz[no] = 1, de[no] = de[fa[no]] + 1;
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(to == fa[no])
            continue;
        fa[to] = no, v1[to] = ter[i].co, dis[to] = dis[no] + ter[i].co;
        dfs1(to);
        sz[no] += sz[to];
        if(son[no] == 0 || sz[to] > sz[son[no]])
            son[no] = to;
    } 
}

void dfs2(int no, int tp)
{
    pos[no] = ++ cnt, v2[cnt] = v1[no], ttp[no] = tp;
    if(son[no] == 0)
        return;
    dfs2(son[no], tp);
    for(ri i = head[no]; i >= 0; i = ter[i].ne)
    {
        int to = ter[i].to;
        if(to == fa[no] || to == son[no])
            continue;
        dfs2(to, to);
    }
}

inline int lca(int x, int y)//求lca的时候就让两个点中较深的跳,一直跳到它们在同一条重链上 
{
    while(ttp[x] != ttp[y])
    {
        if(de[ttp[x]] < de[ttp[y]])
            swap(x, y);
        x = fa[ttp[x]];
    }
    return (de[x] > de[y]) ? y : x;
}

inline void change(int x, int y)//差分 
{
    while(ttp[x] != ttp[y])
    {
        if(de[ttp[x]] < de[ttp[y]])
            swap(x, y);
        s[pos[ttp[x]]] += 1, s[pos[x] + 1] -= 1;//链顶+1,然后在这条链上但是不在两个点路径上的做个-1标记 
        x = fa[ttp[x]];
    }
    if(de[x] > de[y])
        swap(x, y);
    s[pos[x] + 1] += 1, s[pos[y] + 1] -= 1;//和刚才差不多 
}

inline int ask(int x)
{
    int ta = 0, tt = 0, re = -1000000007;
    while(ing[ta + 1].c > x)
        ++ ta;
    if(q[ta] > 0)
        return q[ta];
    memset(s, 0, sizeof(s));
    for(ri i = 1; i <= ta; ++ i)
        change(ing[i].x, ing[i].y);
    for(ri i = 1; i <= n; ++ i)
    {
        tt += s[i];
        if(tt == ta)//选取边权最大的边作为虫洞 
            re = max(re, v2[i]);
    }
    q[ta] = re;
    return re;
}

int main()
{
    memset(head, -1, sizeof(head));
    re(n), re(m);
    for(ri i = 1; i < n; i ++)
        re(lx), re(ly), re(lz), build(lx, ly, lz);
    dfs1(1), dfs2(1, 1);
    for(ri i = 1; i <= m; i ++)
        re(ing[i].x), re(ing[i].y), ing[i].c = dis[ing[i].x] + dis[ing[i].y] - (dis[lca(ing[i].x, ing[i].y)] << 1);
    //提前预处理路径的长度 
    sort(ing + 1, ing + 1 + m, cmp);//按照路径从大到小排 
    int l = 0, r = ing[1].c;
    while(l <= r)//二分 
    {
        int mid = (l + r) >> 1;
        if(ing[1].c - ask(mid) > mid)
            l = mid + 1;
        else
            r = mid - 1, ans = mid;
    }
    printf("%d", ans);
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注