hdu 6201 transaction transaction transaction
2024-10-20 09:22:24
https://vjudge.net/contest/184514#problem/H
题意:
一个商人为了赚钱,在城市之间倒卖商品。有n个城市,每个城市之间有且只有一条无向边连通。给出n个城市的货物的价格,比如A城市是a元,B城市是b元,那么在A买在B卖,赚的钱就是b - a,反之就是 a - b。商人走每条路也需要一定的花费。现在他需要选择某两个城市进行货物的倒卖,问他能获得的最大利润是多少。
思路:
建图的方式非常妙。我们把从A到B的边的权值定义为b - a - v(v为边的权值),从B到A的边的权值定义为a - b - v。依据这个从A到B再到C,就是b - a - v1 加上 c - b - v2,加起来就是c - a - v1 - v2,这样我们就可表示从任意城市到任意城市的距离了。
现在我们要求的就是任意两个城市之间的最大距离。树上最长路并不擅长,所以考虑用最短路求法进行求解。加一个超级源点和超级汇点,跑一遍最短路,就可以了,但是我们求的是最长路。。所以把边取反求最短路就ok了,开始用dijstra跑崩了,忘记了dij不能处理有负权边的图,所以跑了一遍spfa就过了。
这题的主要收获是建图,关键是抵消中间城市对结果的影响。
代码:
#include <stdio.h>
#include <string.h>
#include <vector>
#include <queue>
using namespace std; const int inf = 0x3f3f3f3f; struct edge
{
int from,to;
int cost;
}; vector<edge> edges;
vector<int> v[];
int nodev[];
int dis[];
bool vis[]; void adde(int from,int to,int cost)
{
edge tmp; tmp.from = from;
tmp.to = to;
tmp.cost = -cost; edges.push_back(tmp); int sz = edges.size(); v[from].push_back(sz-);
} void init(int n)
{
for (int i = ;i <= n;i++) v[i].clear(); edges.clear();
} void spfa(void)
{
memset(vis,,sizeof(vis)); memset(dis,inf,sizeof(dis)); queue<int> q; q.push(); dis[] = ; vis[] = ; while (!q.empty())
{
int u = q.front(); q.pop(); vis[u] = ; for (int i = ;i < v[u].size();i++)
{
int id = v[u][i]; int to = edges[id].to; if (dis[to] > dis[u] + edges[id].cost)
{
dis[to] = dis[u] + edges[id].cost; if (!vis[to])
{
q.push(to);
vis[to] = ;
}
}
} }
} int main()
{
int t; scanf("%d",&t); while (t--)
{
int n; scanf("%d",&n); init(n+); for (int i = ;i <= n;i++)
{
scanf("%d",&nodev[i]);
} for (int i = ;i <= n - ;i++)
{
int x,y,z; scanf("%d%d%d",&x,&y,&z); adde(x,y,nodev[y] - nodev[x] - z);
adde(y,x,nodev[x] - nodev[y] - z);
} for (int i = ;i <= n;i++)
{
adde(,i,);
adde(i,n+,);
} spfa(); printf("%d\n",-dis[n+]); //for (int i = 0;i <= n + 1;i++) printf("%d\n",dis[i]);
} return ;
}
最新文章
- Flume官方文档翻译——Flume 1.7.0 User Guide (unreleased version)中一些知识点
- RequireJS shim 用法说明
- 玩转Windows Azure存储服务——高级存储
- 【转】ubuntu64,ndk-r9 编译 ffmpeg 2.1.1的config文件
- UDP广域网,局域网通信-原理分析,穿透技术
- 【BZOJ】【1662】/【POJ】【3252】 【USACO 2006 Nov】Round Number
- [MSDN]关键字查询语言 (KQL) 语法参考
- 8.2.1.3 Range Optimization
- 【C#网络基础】C# get post请求
- Github android客户端源代码分析之一:环境搭建
- CSS3 Test
- codeforce div2 C 树状数组
- FileFilter与FilenameFilter实例
- JavaScript概念总结:作用域、闭包、对象与原型链
- node基础篇一:node介绍、node http、node event 课堂(持续)
- 人脸识别-arcface损失函数
- 2017年java面试题【集合篇】
- mysql 5.6 在线 DDL
- 【Java】基本I/O的学习总结
- CAScrollLayer
热门文章
- tornado 数据库操作
- 【咸鱼教程】本地图片上传。动态GIF表情图生成
- github中删除一个repository
- 2-sat入门(tarjan)hdu(3062)
- 关于JavaScript转义字符(&#39;、 "; 、\"; 、\&#39;)【原创】
- python模块路径
- Linux下实现秒级定时任务的两种方案
- Django的URL name 学习
- CCCC L2-013. 红色警报 连通分量
- centos 7 yum configuration; yum localinstall