题解【luogu P2680 NOIp提高组2015 运输计划】

题解

题意

一棵树上有\(m\)条路径，可以将其中一条边的权值改为0，问最长的路径最短是多少

分析

最短的路径最长自然想到二分最长路径，设其为\(dis\)
关键在于如何check
check的关键又是将哪条边改为0
贪心，如果所有超过\(dis\)的路径能在一条边上重合，则将那条边改为0，之后再判断改为0后是否最大的路径小于\(dis\)；若无法将所有超过\(dis\)的边重合在一条边上，直接return false;

做法

算两个点之间的路径长用dfs + LCA来实现
判断路径之间的重合用树上差分来实现
这里用的是倍增

注意事项

无向边要把数组开两倍！！！

代码

#include <iostream>

#include <cstdlib>

#include <cstdio>

#include <cstring>

using namespace std;

const int MAXN = 500500;

int n, m;

int logn;

int u[MAXN], v[MAXN], lca[MAXN];

int vis[MAXN], dep[MAXN], fa[MAXN][25];

int dfn[MAXN], Index, Edge_cnt;

int Max_dis = -1, treeC[MAXN], predis[MAXN], dissum[MAXN], distence[MAXN];

int ecnt;

struct node

{

    int v;

    int w;

    node *next;

}pool[MAXN << 1], *head[MAXN << 1];

void addedge(int u, int v, int w)

{

    node *p = &pool[++ecnt], *q = &pool[++ecnt];

    p->v = v, p->w = w, p->next = head[u], head[u] = p;

    q->v = u, q->w = w, q->next = head[v], head[v] = q;

}

void dfs(int u)

{

    int v;

    dfn[++Index] = u;

    vis[u] = 1;

    for(node *p = head[u]; p; p = p->next)

        if(!vis[v = p->v])

        {

        	dep[v] = dep[u] + 1;

        	dissum[v] = dissum[u] + p->w;

        	fa[v][0] = u;

        	predis[v] = p->w;

        	dfs(v);

        }

}

int LCA(int u, int v)

{

    if(dep[u] < dep[v]) swap(u, v);

    for(int i = 20; i >= 0; i--)

        if(fa[u][i] != 0 && dep[fa[u][i]] >= dep[v])

            u = fa[u][i];

    if(u == v) return u;

    for(int i = 20; i >= 0; i--)

        if(fa[u][i] != fa[v][i])

            u = fa[u][i], v = fa[v][i];

    return fa[u][0];

}

bool check(int dis)

{

    memset(treeC, 0, sizeof(treeC));

    Edge_cnt = 0;

    for(int i = 1; i <= m; i++)

        if(distence[i] > dis)

        {

        	++Edge_cnt;

        	treeC[u[i]]++;

        	treeC[v[i]]++;

        	treeC[lca[i]] -= 2;

        }

    for(int i = n; i >= 1; i--)

    {

    	int t = dfn[i];

    	treeC[fa[t][0]] += treeC[t];

    	if(dis >= Max_dis - predis[t] && treeC[t] == Edge_cnt)

    	    return true;

    }

    return false;

}

int main()

{

    scanf("%d%d", &n, &m);

    for(int i = 1; i <= n - 1; i++)

    {

        int u, v, w;

        scanf("%d%d%d", &u, &v, &w);

        addedge(u, v, w);

    }

    dep[1] = 1, dep[0] = -1;

    dfs(1);

	for(int j = 1; j <= 20; j++)

        for(int i = 1; i <= n; i++)

            fa[i][j] = fa[fa[i][j - 1]][j - 1];

    for(int i = 1; i <= m; i++)

    {

        scanf("%d%d", &u[i], &v[i]);

        lca[i] = LCA(u[i], v[i]);

        distence[i] = dissum[u[i]] + dissum[v[i]] - dissum[lca[i]] * 2;

        Max_dis = max(Max_dis, distence[i]);

    }

    int ans = -1;

    int l = 0, r = Max_dis;

    while(l <= r)

    {

        int mid = (l + r) / 2;

        if(check(mid)) r = mid - 1, ans = mid;

        else l = mid + 1;

    }

    printf("%d\n", ans);

    return 0;

}

巴特西

题解【luogu P2680 NOIp提高组2015 运输计划】

无向边要把数组开两倍！！！

最新文章

热门文章

巴特西

题解 【luogu P2680 NOIp提高组2015 运输计划】

无向边要把数组开两倍！！！

最新文章

热门文章

题解【luogu P2680 NOIp提高组2015 运输计划】