A simple Blog for wyx I've been down the bottle hoping.
POJ 1935 Journey 树形dp+简单构造
发表于: | 分类: Oi | 评论:0 | 阅读:45

这题的意思就是给你一个树,一些点和一个根,从根出发遍历给定的点,最后不必回根的最小路径
这就是一个简单构造,没必要往难了想
答案显然是先忽略不回根的情况,再在选定的点中找到一个距离$root$最远的……
开始我还想怎么求那个和,后来发现深搜的时候扫一下就行了,如果这个点要选,那么就加上他和父亲连边的边权*2,然后再将父亲标记为$need$,由于是深搜,只有回溯的时候才会加上这条边,不会加重
时间复杂度$O(m+n)$

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define N 50000+5
#define M 100000+5
const int inf = 0x7fffff;
using namespace std;

int head[N];

inline int read()
{
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

struct graph
{
    int next,to,val;
    graph () {}
    graph (int _next,int _to,int _val)
    :next(_next),to(_to),val(_val){}
}edge[M];

inline void add(int x,int y,int z)
{
    static int cnt = 0;
    edge[++cnt] = graph(head[x],y,z);
    head[x] = cnt;
    edge[++cnt] = graph(head[y],x,z);
    head[y] = cnt;
}

int dis[N];
int sum;
bool need[N];

void DFS(int x,int fa)
{
    for(int i=head[x];i;i=edge[i].next)
        if(edge[i].to!=fa)
        {
            dis[edge[i].to] = dis[x]+edge[i].val;
            DFS(edge[i].to,x);
            if(need[edge[i].to]){sum += (edge[i].val<<1);need[x] = 1;}
        }
}

int main()
{
    int n = read(),root = read();
    for(int i=1;i<n;++i)
    {
        int x = read(),y=read(),z=read();
        add(x,y,z);
    }
    int m = read();
    for(int i=1,tmp;i<=m;++i)
        tmp = read(),need[tmp] = 1;
    DFS(root,root);
    int MAX = 0;
    for(int i=1;i<=n;++i)
        if(need[i])
            MAX = max(MAX,dis[i]);
    cout<<sum-MAX;
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP