Codeforces Round #586 (Div. 1 + Div. 2) E. Tourism
链接:
https://codeforces.com/contest/1220/problem/E
题意:
Alex decided to go on a touristic trip over the country.
For simplicity let's assume that the country has n cities and m bidirectional roads connecting them. Alex lives in city s and initially located in it. To compare different cities Alex assigned each city a score wi which is as high as interesting city seems to Alex.
Alex believes that his trip will be interesting only if he will not use any road twice in a row. That is if Alex came to city v from city u, he may choose as the next city in the trip any city connected with v by the road, except for the city u.
Your task is to help Alex plan his city in a way that maximizes total score over all cities he visited. Note that for each city its score is counted at most once, even if Alex been there several times during his trip.
思路:
题意是不能立即原路返回, 而是绕一下可以原路返回..以为是每条边只能走一次.
这样的话看别人代码, 考虑Dfs, 记录存不存在一个链最底下有没有环存在, 如果有就可以返回上来, 吧点值累计到答案.
如果不行吧最长不能返回的链值单独记录, 然后不停地往上去更新, 更新出一个值最大的链即可.
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 2e5+10;
vector<int> G[MAXN];
LL Other[MAXN], Val[MAXN], res = 0;
int Vis[MAXN];
int n, m, s;
bool Dfs(int u, int fa)
{
Vis[u] = 1;
bool flag = false;
for (int i = 0;i < G[u].size();i++)
{
int node = G[u][i];
if (node == fa)
continue;
if (Vis[node] == 1)
{
flag = true;
continue;
}
bool Tmp = Dfs(node, u);
if (Tmp)
flag = true;
Other[u] = max(Other[u], Other[node]);
}
if (flag)
{
res += Val[u];
return true;
}
else
{
Other[u] += Val[u];
return false;
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m;
for (int i = 1;i <= n;i++)
cin >> Val[i];
int u, v;
for (int i = 1;i <= m;i++)
{
cin >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
cin >> s;
Dfs(s, 0);
cout << res+Other[s] << endl;
return 0;
}
最新文章
- Hadoop入门学习笔记---part4
- python列表模拟堆栈和队列
- 05.virsh命令的常用操作(kvm)
- jQuery触发a标签点击事件-为什么不跳转
- Android开发学习笔记:浅谈显示Intent和隐式Intent
- CentOS 下JDK安装
- 2012 #1 Saving Princess claire_
- 关于webapi 返回的类型的笔记
- Android设备定制为永不锁屏
- 保存mysql用户的登录信息到~.my.cnf文件;用于方便登录操作。
- jupyter nootbook本地使用指南
- 安装Visual Studio 语言包时出现windows 程序兼容模式已打开.请将其关闭
- MVC+EF 多条件查询
- 架构(四)Git简介,安装以及相关命令SourceTree
- 3ds max学习笔记-- 动画
- Oracle11默认用户名和密码
- 如何打印一棵树(Java)
- spring注解之@Lazy
- EJB2.0 ejb-jar.xml配置文件详解
- 【WIN10】WIN2D——基本圖形的繪製