算法进阶指南图论 最优贸易

这篇具有很好参考价值的文章主要介绍了算法进阶指南图论 最优贸易。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

最优贸易

题目描述

C C C 国有 n n n 个大城市和 m m m 条道路,每条道路连接这 n n n 个城市中的某两个城市。任意两个城市之间最多只有一条道路直接相连。这 m m m 条道路中有一部分为单向通行的道路,一部分为双向通行的道路,双向通行的道路在统计条数时也计为 1 1 1 条。

C C C 国幅员辽阔,各地的资源分布情况各不相同,这就导致了同一种商品在不同城市的价格不一定相同。但是,同一种商品在同一个城市的买入价和卖出价始终是相同的。

商人阿龙来到 C C C 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后,便决定在旅游的同时,利用商品在不同城市中的差价赚回一点旅费。设 C C C n n n 个城市的标号从 1 ∼ n 1\sim n 1n,阿龙决定从 1 1 1 号城市出发,并最终在 n n n 号城市结束自己的旅行。在旅游的过程中,任何城市可以重复经过多次,但不要求经过所有 n n n 个城市。阿龙通过这样的贸易方式赚取旅费:他会选择一个经过的城市买入他最喜欢的商品――水晶球,并在之后经过的另一个城市卖出这个水晶球,用赚取的差价当做旅费。由于阿龙主要是来 C C C 国旅游,他决定这个贸易只进行最多一次,当然,在赚不到差价的情况下他就无需进行贸易。

假设 C C C 国有 5 5 5 个大城市,城市的编号和道路连接情况如下图,单向箭头表示这条道路为单向通行,双向箭头表示这条道路为双向通行。

算法进阶指南图论 最优贸易,算法进阶指南,图论,# 连通分量,算法,图论

假设 1 ∼ n 1\sim n 1n 号城市的水晶球价格分别为 4 , 3 , 5 , 6 , 1 4,3,5,6,1 4,3,5,6,1

阿龙可以选择如下一条线路: 1 → 2 → 3 → 5 1\to2\to3\to5 1235,并在 2 2 2 号城市以 3 3 3 的价格买入水晶球,在 3 3 3 号城市以 5 5 5 的价格卖出水晶球,赚取的旅费数为 2 2 2

阿龙也可以选择如下一条线路: 1 → 4 → 5 → 4 → 5 1\to4\to5\to4\to5 14545,并在第 1 1 1 次到达 5 5 5 号城市时以 1 1 1 的价格买入水晶球,在第 2 2 2 次到达 4 4 4 号城市时以 6 6 6 的价格卖出水晶球,赚取的旅费数为 5 5 5

现在给出 n n n 个城市的水晶球价格, m m m 条道路的信息(每条道路所连接的两个城市的编号以及该条道路的通行情况)。请你告诉阿龙,他最多能赚取多少旅费。

输入格式

第一行包含 2 2 2 个正整数 n n n m m m,中间用一个空格隔开,分别表示城市的数目和道路的数目。

第二行 n n n 个正整数,每两个整数之间用一个空格隔开,按标号顺序分别表示这 n n n 个城市的商品价格。

接下来 m m m 行,每行有 3 3 3 个正整数 x , y , z x,y,z x,y,z,每两个整数之间用一个空格隔开。如果 z = 1 z=1 z=1,表示这条道路是城市 x x x 到城市 y y y 之间的单向道路;如果 z = 2 z=2 z=2,表示这条道路为城市 x x x 和城市 y y y 之间的双向道路。

输出格式

一个整数,表示最多能赚取的旅费。如果没有进行贸易,则输出 0 0 0

样例 #1

样例输入 #1

5 5 
4 3 5 6 1 
1 2 1 
1 4 1 
2 3 2 
3 5 1 
4 5 2

样例输出 #1

5

提示

【数据范围】

输入数据保证 1 1 1 号城市可以到达 n n n 号城市。

对于 10 % 10\% 10% 的数据, 1 ≤ n ≤ 6 1\leq n\leq 6 1n6

对于 30 % 30\% 30% 的数据, 1 ≤ n ≤ 100 1\leq n\leq 100 1n100

对于 50 % 50\% 50% 的数据,不存在一条旅游路线,可以从一个城市出发,再回到这个城市。

对于 100 % 100\% 100% 的数据, 1 ≤ n ≤ 100000 1\leq n\leq 100000 1n100000 1 ≤ m ≤ 500000 1\leq m\leq 500000 1m500000 1 ≤ x , y ≤ n 1\leq x,y\leq n 1x,yn 1 ≤ z ≤ 2 1\leq z\leq 2 1z2,$1\leq $ 各城市的编号 ≤ n \leq n n

水晶球价格 ≤ 100 \leq 100 100

思路一:

考虑分层图,因为每个点有两种状态,为买入和卖出,所以我们可以建三层图,平行层之间的边权为0,从第一层到 第二层由当前点 u u u u + n u+n u+n连一条边,表示买入,边权为 − w -w w,同理,我们由 u + n u+n u+n u + n ∗ 2 u+n*2 u+n2连一条价值为 w w w的边,表示卖出。然后对整个图去跑最长路即可(因为题目说要价值最大)

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9+7;
const int maxv = 4e6 + 5;
// #define endl "\n"

int n,m;

vector<pll> e[N];

void add(int u,int v,int w)
{
	e[u].push_back({v,w});
}

int st[N];
int d[N];
void spfa()
{
    memset(d,0x3f,sizeof(d));
    d[1]=0;
    queue<int> q;
    q.push(1);
    st[1]=1;
    while(!q.empty()){
        int t=q.front();
        q.pop();
        st[t]=0;
        int i;
        for(auto v:e[t]){
            int b=v.first;
            int w=v.second;
            if(d[b]>d[t]+w){
                d[b]=d[t]+w;
                if(!st[b]){
                q.push(b);
                st[b]=1;
                }
            }
        }
    }
}

void solve()
{
	cin>>n>>m;
	vector<int> a(n+5);
	for(int i=1;i<=n;i++) cin>>a[i],add(i,i+n,-a[i]),add(i+n,i+2*n,a[i]);
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		add(x,y,0);
		add(x+n,y+n,0);
		add(x+n*2,y+n*2,0);
		if(z==2){
			add(y,x,0);
			add(y+n,x+n,0);
			add(y+n*2,x+n*2,0);
		}
	}
	spfa();
	cout<<d[n]<<endl;
}

int main()
{
    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t=1;
	//cin>>t;
	while(t--){
		solve();
	}
   	system("pause");
    return 0;
}

思路二:

强连通分量缩点然后进行dp。
初始想法,我们考虑若其为DAG,那么我们可以直接进行DP,但又因为肯定存在环,所以可以对其进行强连通分量缩点。

因为缩完点后为DAG,即有向无环图,而我们对于有向无环图可以直接进行dp,同时我们还可以知道每个强连通分量的最小价值和最大价值,那么我们用dp处理出从 1 号点开始,能到达所有点的最小买入价值,然后用该点的卖出价值减去买入价值,最后对其取max即可。文章来源地址https://www.toymoban.com/news/detail-827171.html

#include <bits/stdc++.h>

using namespace std;
const int N = 1e5 + 5;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef array<ll, 3> p3;
int mod = 1e9+7;
// const int maxv = 4e6 + 5;
// #define endl "\n"
int n, m, tot, dfsn[N], ins[N], low[N];
stack<int> s;
vector<int> e[N], e2[N],e3[N];//分别用来存初始图,缩点后的图,缩点后的图对应的反图
vector<vector<int>> scc;
vector<int> b(N);
int a[N];
int minv[N],maxv[N];

struct node
{
	int u,v,z;
}h[N];


void dfs(int x)
{
	low[x] = dfsn[x] = ++tot, ins[x] = 1, s.push(x);
	for (auto u : e[x])
	{
		if (!dfsn[u])
		{
			dfs(u);
			low[x] = min(low[x], low[u]);
		}
		else if (ins[u])
			low[x] = min(low[x], dfsn[u]);
	}
	if (dfsn[x] == low[x])
	{
		vector<int> c;
		while (1)
		{
			auto t = s.top();
			c.push_back(t);
			ins[t] = 0;
			s.pop();
			b[t] = scc.size();
			int sz=scc.size();
			minv[sz]=min(minv[sz],a[t]);
			maxv[sz]=max(maxv[sz],a[t]);
			if (t == x)
				break;
		}
		scc.push_back(c);
	}
}

void add(int u, int v)
{
	e[u].push_back(v);
}

bool vis[N];

void dfs2(int x)
{
	vis[x]=1;
	for(auto u: e3[x])
		if(!vis[u]) dfs2(u);
}

void solve()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++) cin>>a[i];
	for(int i=1;i<=m;i++){
		int u,v,z;
		cin>>u>>v>>z;
		h[i]={u,v,z};
		add(u,v);
		if(z==2) add(v,u);
	}
	memset(minv,0x3f,sizeof minv);
	for(int i=1;i<=n;i++){
		if(!dfsn[i]){
			dfs(i);
		}
	}
	//缩点过程
	for(int i=1;i<=m;i++){
		auto [u,v,z]=h[i];
		int x=b[u],y=b[v];
		if(x!=y) {
			e2[x].push_back(y),e3[y].push_back(x);
			if(z==2) e2[y].push_back(x),e3[x].push_back(y);//同时注意因为题目中说存在双向边,所以在缩点后的建图中同样也需要建立
		}
	}
	vector<int> dp(n+5);
	for(int i=0;i<scc.size();i++) dp[i]=minv[i];
	int st=b[1];
	int ed=b[n];
	dfs2(ed);//因为要确保能到达n点,所以从n开始进行dfs搜索能够到达的点,由此需要缩点后的反图
	int ans=0;
	for(int i=st;i>=0;i--){//从1号点开始,强连通分量即为逆拓扑序
		if(vis[i]) {
			ans=max(ans,maxv[i]-dp[i]);
		}
		for(auto u: e2[i]){
			dp[u]=min(dp[u],dp[i]);
		}
	}
	cout<<ans<<endl;
}

int main()
{
    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	int t;
	t=1;
	//cin>>t;
	while(t--){
		solve();
	}
   	system("pause");
    return 0;
}

到了这里,关于算法进阶指南图论 最优贸易的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 图论——强连通分量详解!

    本篇主要内容: 强连通分量等概念 Tarjan算法的过程与实现 首先我们要明白上面是 连通 。 在一张图中 任意 两个点能 互相 到达。(举个例子) 所以我们称上面的这个图是一个 连通图 !  接着我们在来理解什么是 强连通 。 若一张 有向图 的节点两两互相可达,则称这张图

    2024年02月07日
    浏览(34)
  • 【图论】强连通分量

    ​  强连通分量(Strongly Connected Components,简称SCC)是图论中的一个概念,用于描述有向图中的一组顶点,其中任意两个顶点之间都存在一条有向路径。换句话说,对于图中的任意两个顶点u和v,如果存在一条从u到v的有向路径,同时也存在一条从v到u的有向路径,那么u和v就属

    2024年02月14日
    浏览(40)
  • 第三章 图论 No.9有向图的强连通与半连通分量

    连通分量是无向图的概念,yxc说错了,不要被误导 强连通分量:在一个有向图中,对于分量中的任意两点u,v,一定能从u走到v,且能从v走到u。强连通分量是一些点的集合,若加入其他点,强连通分量中的任意两点就不能互相递达 半连通分量:在一个有向图中,对于分量中

    2024年02月13日
    浏览(47)
  • 有向图的强连通分量算法

    有向图的强连通分量算法 强连通分量定义 在有向图中,某个子集中的顶点可以直接或者间接互相可达,那么这个子集就是此有向图的一个强连通分量,值得注意的是,一旦某个节点划分为特定的强连通分量后,此顶点不能在其它子树中重复使用,隐含了图的遍历过程和极大

    2024年02月06日
    浏览(71)
  • 《算法竞赛进阶指南》------图论篇

    Telephone Lines 题意:从1到N修一条电缆,有p对电线杆之间是可以连接的,电信公司可以提供k条电缆,其他的由John提供,求john提供的电缆的最长的那根的长度(ret)。 思路:实则是求最短最长的边。 二分结果(sum)。对于 边值sum, 电信公司需要提供电缆。 用djk 计算 1-n 路径上的

    2024年02月03日
    浏览(35)
  • 【图论】无向图连通性(tarjan算法)

    1. 连通 : 在图论中,连通性是指一个无向图中的任意两个顶点之间存在路径。如果对于图中的任意两个顶点 u 和 v,存在一条路径从 u 到 v,那么图被称为连通图。如果图不是连通的,那么它可以被分为多个 连通分量 ,每个连通分量都是一个连通子图。 2.割点: 割点(Cut V

    2024年02月13日
    浏览(40)
  • 有向图的强连通分量

    对于一个有向图,连通分量:对于分量中任意两点u,v,必然可以从u走到v,且从v走到u. 强连通分量:极大连通分量。 求出强连通分量后,可以通过将强连通分量缩点的方式,将有向图转化成有向无环图。 求强连通分量的方法:tarjan O(n+m),时间复杂度是线性的 1 . 采用dfs来遍历整

    2024年02月10日
    浏览(36)
  • 图的基本概念辨析,包括连通图、极大连通子图、连通分量、强连通图、极大强连通子图等

    概念(1-4)都是针对无向图的   图中从一个顶点到达另一顶点,若存在至少一条路径,则称这两个顶点是连通着的。例如图 1 中,虽然 V1 和 V3 没有直接关联,但从 V1 到 V3 存在两条路径,分别是 V1-›V2-›V3 和 V1-›V4-›V3,因此称 V1 和 V3 之间是连通的。 图 1 顶点之间的连

    2024年02月15日
    浏览(56)
  • 图论第一次作业(教材:图论与网络最优化算法龚劬编著)

    5.证明K维超立方体 的顶点是 ,边数是 ,且是二部图,其中, 的顶点集 ,且两顶点相邻当且仅当着两个k维序列正好有一对应项不相同。 8.任何两个以上的人组成的人群中,至少有两个人,他们的朋友数一样多。 11.设 是平面上的点集,其中任意两点间的距离至少是1,证明:

    2024年02月08日
    浏览(42)
  • 【计算机算法】【图论】【最优匹配与点云对准问题】最(极)大团算法

    团与最大团的定义 图顶点集的子集满足任意两个顶点相邻,称该子集是该图的一个团。图的所有团中顶点最多的,即最大的一个或多个,称为图的最大团或极大团。 图的最大团的实际应用问题 CVPR2023最佳论文之一用最大团算法实现鲁棒的点云对准,有效解决外点问题。顾名

    2024年03月15日
    浏览(37)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包