首页 > 其他 > 详细

Codeforces Round #586 (Div. 1 + Div. 2) E. Tourism

时间:2019-10-06 17:43:00      阅读:61      评论:0      收藏:0      [点我收藏+]

https://codeforces.com/contest/1220/problem/E

//思路:由题可知,不能往回走,因此先找出所有的叶子节点,从叶子节点往root根节点去搜索,碰见环则停止,因为在环中的节点是一定可以相互到达的,因此就不会存在一个选择问题

//最后把所有环中的节点w[i]累加和能到达的一条最大支路算出即可

#include<bits/stdc++.h>
using namespace std;
typedef long long i64;
const int maxn = 2e5 + 32;
int wi[maxn],edge[maxn];
i64 cnt[maxn];
queue<int> q;
vector<int> Grape[maxn];
int main()
{
    ios::sync_with_stdio(false); cin.tie(0),cout.tie(0);
    int n,m,u,v,root;
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        cin>>wi[i];
    for(int i=1;i<=m;++i)
    {
        cin>>u>>v;
        Grape[u].push_back(v);
        Grape[v].push_back(u);
        ++edge[u],++edge[v];
    }
    cin>>root;
    for(int i=1;i<=n;++i)
        if(edge[i] == 1&&i != root)
            q.push(i);//放入叶子节点
    while(!q.empty())
    {
        int u = q.front();  q.pop();
        edge[u] = -1;
        for(auto nxt: Grape[u])
        {
            if(edge[nxt] == -1)
                continue;
            --edge[nxt];
            cnt[nxt] = max(cnt[nxt],cnt[u]+wi[u]);
            if(edge[nxt] == 1&& nxt != root)
                q.push(nxt);
        }
    }
    i64 sum = 0,maxValue = 0;
    for(int i=1;i<=n;++i)
        if(edge[i]!=-1)
        {
            sum += wi[i];
            maxValue = max(maxValue,cnt[i]);
        }
    cout<<sum + maxValue <<\n;
}

 

Codeforces Round #586 (Div. 1 + Div. 2) E. Tourism

原文:https://www.cnblogs.com/newstartCY/p/11627773.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!