看到这个题,原本想先从后往前dfs,求出能到终点的点,再在这些点里从前往后spfa,用一条边上的两个城市的商品价格的差来作边权,实施过后,发现图中既有负边权,又有回路,以及各种奇奇怪怪的东西。说实话我连样例都没过,然后提交一下试试,得了10分。
然而我发现,要求赚最多钱,就是到那个点的路径上的最大价格 - 最小价格。
两边dfs——
最小价格可以从前往后搜来算。
最大价格可以从后往前搜来算。
最后枚举一边所有点maxx - minn的最大值就好。
说出来你可能不信,我是看的题解。
——代码
#include <cstdio>
#include <cstring>
#include <queue>
#include <iostream> using namespace std; int n, m, cnt1, cnt2, ans;
int a[], next1[], to1[], head1[], next2[], to2[],
head2[], maxx[], minn[]; inline void add1(int x, int y)
{
to1[cnt1] = y;
next1[cnt1] = head1[x];
head1[x] = cnt1++;
} inline void add2(int x, int y)
{
to2[cnt2] = y;
next2[cnt2] = head2[x];
head2[x] = cnt2++;
} inline void dfs2(int u, int k)
{
int i, v;
maxx[u] = max(maxx[u], k);
for(i = head2[u]; i != -; i = next2[i])
{
v = to2[i];
if(maxx[v] < k) dfs2(v, max(k, a[v]));
}
} inline void dfs1(int u, int k)
{
int i, v;
minn[u] = min(minn[u], k);
for(i = head1[u]; i != -; i = next1[i])
{
v = to1[i];
if(minn[v] > k) dfs1(v, min(k, a[v]));
}
} int main()
{
int i, j, x, y, z;
memset(head1, -, sizeof(head1));
memset(head2, -, sizeof(head2));
scanf("%d %d", &n, &m);
for(i = ; i <= n; i++)
{
scanf("%d", &a[i]);
maxx[i] = -1e9;
minn[i] = 1e9;
}
for(i = ; i <= m; i++)
{
scanf("%d %d %d", &x, &y, &z);
if(z == )
{
add1(x, y);
add1(y, x);
add2(x, y);
add2(y, x);
}
else
{
add1(x, y);
add2(y, x);
}
}
dfs1(, a[]);
dfs2(n, a[n]);
for(i = ; i <= n; i++) ans = max(ans, maxx[i] - minn[i]);
printf("%d", ans);
return ;
}
其中dfs不用设置vis来记录是否被访问过,因为有双向道路,所以走到一个点有可能会返回来,所以进行深搜的判断标准是目标点(姑且这么说吧)的最大最小值小于或大于当前点的最大最小值。这样即使走到后面的点,发现前面的点需要修改,也可以改回去。
也可以用 spfa ,改变一下松弛操作,dis 数组表示到当前点的路径上买入的最小值,最后统计一遍就行。
——代码
#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream> using namespace std; const int MAXN = ;
int n, m, cnt, cnt1, ans;
int a[MAXN], head[MAXN], to[MAXN], next[MAXN], head1[MAXN], to1[MAXN], next1[MAXN], dis[MAXN];
bool b[MAXN], vis[MAXN];
queue <int> q; inline void add(int x, int y)
{
to[cnt] = y;
next[cnt] = head[x];
head[x] = cnt++;
} inline void add1(int x, int y)
{
to1[cnt1] = y;
next1[cnt1] = head1[x];
head1[x] = cnt1++;
} inline void dfs(int u)
{
int i, v;
b[u] = ;
for(i = head1[u]; i != -; i = next1[i])
{
v = to1[i];
if(!b[v]) dfs(v);
}
} inline void spfa(int u)
{
int i, v;
memset(dis, / , sizeof(dis));
q.push(u);
dis[u] = a[u];
while(!q.empty())
{
u = q.front();
q.pop();
vis[u] = ;
for(i = head[u]; i != -; i = next[i])
{
v = to[i];
if(dis[v] > min(dis[u], a[v]) && b[v])
{
dis[v] = min(dis[u], a[v]);
if(!vis[v])
{
q.push(v);
vis[v] = ;
}
}
}
}
} int main()
{
int i, j, x, y, z;
scanf("%d %d", &n, &m);
for(i = ; i <= n; i++) scanf("%d", &a[i]);
memset(head, -, sizeof(head));
memset(head1, -, sizeof(head1));
for(i = ; i <= m; i++)
{
scanf("%d %d %d", &x, &y, &z);
if(z == )
{
add(x, y);
add1(y, x);
}
else
{
add(x, y);
add(y, x);
add1(x, y);
add1(y, x);
}
}
dfs(n);
spfa();
for(i = ; i <= n; i++)
if(b[i])
ans = max(ans, a[i] - dis[i]);
printf("%d", ans);
return ;
}
NOIP2009T3最优贸易的更多相关文章
-
NOIP2009T3最优贸易(Dfs + spfa)
洛谷传送门 看到这个题,原本想先从后往前dfs,求出能到终点的点,再在这些点里从前往后spfa,用一条边上的两个城市的商品价格的差来作边权,实施过后,发现图中既有负边权,又有回路,以及各种奇奇怪怪的东 ...
-
NOIP2009 最优贸易
3. 最优贸易 (trade.pas/c/cpp) [问题描述] C 国有 n 个大城市和 m 条道路,每条道路连接这 n 个城市中的某两个城市.任意两个城市之间 多只有一条道路直接相连.这 m 条道 ...
-
Codevs 1173 最优贸易 2009年NOIP全国联赛提高组
1173 最优贸易 2009年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目描述 Description [问题描述] C 国有n ...
-
Luogu P1073 最优贸易
题目描述 C 国有 n 个大城市和 m 条道路,每条道路连接这 n 个城市中的某两个城市.任意两个城市之间最多只有一条道路直接相连.这 m 条道路中有一部分为单向通行的道路,一部分为双向通行的道路,双 ...
-
洛谷 P1073 最优贸易 解题报告
P1073 最优贸易 题目描述 \(C\)国有\(n\)个大城市和\(m\)条道路,每条道路连接这\(n\)个城市中的某两个城市.任意两个城市之间最多只有一条道路直接相连.这\(m\)条道路中有一部分 ...
-
CH6101 最优贸易【最短路】
6101 最优贸易 0x60「图论」例题 描述 C国有 n 个大城市和 m 条道路,每条道路连接这 n 个城市中的某两个城市.任意两个城市之间最多只有一条道路直接相连.这 m 条道路中有一部分为单向通 ...
-
[Luogu 1073] NOIP2009 最优贸易
[Luogu 1073] NOIP2009 最优贸易 分层图,跑最长路. 真不是我恋旧,是我写的 Dijkstra 求不出正确的最长路,我才铤而走险写 SPFA 的- #include <alg ...
-
洛谷P1073 最优贸易 [图论,DP]
题目传送门 最优贸易 题目描述 C 国有n 个大城市和m 条道路,每条道路连接这n 个城市中的某两个城市.任意两个城市之间最多只有一条道路直接相连.这m 条道路中有一部分为单向通行的道路,一部分为双向 ...
-
【洛谷P1073】[NOIP2009]最优贸易
最优贸易 题目链接 看题解后感觉分层图好像非常NB巧妙 建三层n个点的图,每层图对应的边相连,权值为0 即从一个城市到另一个城市,不进行交易的收益为0 第一层的点连向第二层对应的点的边权为-w[i], ...
随机推荐
-
Android Activity和Fragment的转场动画
Android Activity和Fragment的转场动画 Activity转场动画 Activity的转场动画是通过overridePendingTransition(int enterAnim, ...
-
sql分页代码
//三种sql分页语句 SELECT TOP 分页尺寸 * FROM ( SELECT ROW_NUMBER() OVER (ORDER BY id) AS RowNumber,* FROM Blob ...
-
什么叫CallBack函数,怎么用回调函数?
JQuery众多常用方法中很经常会用到回调函数, 理解好js callback函数定义及用法,我们就可以利用callback函数帮我们做很多事情啦! A callback is a function ...
-
《C++ Primer Plus》学习笔记10
<C++ Primer Plus>学习笔记10 <<<<<<<<<<<<<<<<<&l ...
-
Flex表格中添加图片
Flex4.5中datagrid加入图片显示image <s:DataGrid id="maingrid" x="0" y="36" ...
-
【SSH系列】Hibernate映射 -- 一对一单向关联映射
映射原理 一对一关联映射:两个实体对象之间是一对一的关联映射,即一个对象只能与另外唯一的一个对象相对应.有两种策略可以实现一对一的关联映射: a.主键关联:即让两个对象具有相 ...
-
腾讯开源 MMKV — 基于mmap的高性能通用key-value组件
一.介绍 MMKV 是基于 mmap 内存映射的 key-value 组件,底层序列化/反序列化使用 protobuf 实现,性能高,稳定性强.从 2015 年中至今,在 iOS 微信上使用已有近 3 ...
-
MySQL数据库性能优化思路与解决方法(二转)
原文:http://bbs.landingbj.com/t-0-242512-1.html 1.锁定表 尽管事务是维护数据库完整性的一个非常好的方法,但却因为它的独占性,有时会影响数据库的性能,尤其是 ...
-
gulp下单页面应用打包
项目地址:https://pan.baidu.com/s/1cu4WW2 之前已经说过多入口打包,最近正好做一个单页面应用,之前多人口是用webpack打包的,但是感觉webpack比较重,单页面我又 ...
-
Delphi - 子窗体继承父窗体后如何显示父窗体上的控件
1.创建子窗体Form1 File -> New -> Form,新建一个form,在form的单元文件中修改 2.子窗体中引用父窗体单元 uses TFatherForm 3.将子窗体中 ...