最优贸易

题目链接

题目描述

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

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

商人阿龙来到 C 国旅游。当他得知同一种商品在不同城市的价格可能会不同这一信息之后,便决定在旅游的同时,利用商品在不同城市中的差价赚回一点旅费。设 C 国 \(1~n\) 个城市的标号从 ,阿龙决定从 \(1\) 号城市出发,并最终在 \(n\) 号城市结束自己的旅行。在旅游的过程中,任何城市可以重复经过多次,但不要求经过所有 个城市。

阿龙通过这样的贸易方式赚取旅费:他会选择一个经过的城市买入他最喜欢的商品——水晶球,并在之后经过的另一个城市卖出这个水晶球,用赚取的差价当做旅费。由于阿龙主要是来 C 国旅游,他决定这个贸易只进行最多一次,当然,在赚不到差价的情况下他就无需进行贸易。

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

最优贸易

假设 \(1\)~\(n\) 号城市的水晶球价格分别为 \(4, 3, 6, 5, 1\) 。

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

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

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

输入格式

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

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

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

输出格式

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

样例输出

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

样例输出

5

数据范围与提示

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

对于 \(10\%\) 的数据,\(1≤n≤6\)。

对于 \(30\%\) 的数据,\(1≤n≤100\)。

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

对于 \(100\%\) 的数据,\(1≤n≤100000\),\(1≤m≤500000\),\(1≤x\),\(y≤n\),\(1≤z≤2\),\(1≤\)各城市

水晶球价格 \(≤100\)。

0x01 前置芝士

又来水题解了呢。

比较老的一道真题了,之前也做过一次,算是旧题重做吧。

所用知识点:dp,拓扑排序,spfa,分层图思想,tarjan(?


0x02 关于部分分

最近的联赛让我有了看部分分的习惯。

首先这道题我们可以抽象成这样一个命题:

一张图中,任意一点 \(x\), 求从 \(1\) 走到 \(n\) 并且过点 \(x\) 的路径上,点 \(x\) 前面的最小点权,与点 \(x\) 后面的最大点权的差的最大值。(简单贪心可证。我们需要让进价少,售价大。

也就是说对于一个点 \(x\),我们只需要算出 \(ma[x]\) 与 \(mi[x]\) 即可,\(ma[x]\) 表示点 \(x\) 到 \(n\) 的所有路径中的最大点权,\(mi[x]\) 表示点 \(1\) 到 \(x\) 的所有路径的最小点权。

又因为这道题保证有 \(50pt\) 无环。于是直接两次拓扑,一次正一次反即可。

#include <cstdio>
#include <queue>
using namespace std;

inline int Max(int x, int y) { return x > y ? x : y; }
inline int Min(int x, int y) { return x < y ? x : y; }
const int MAXN = 1e5 + 5;
const int MAXE = 5e5 * 2 + 5;

int lenf = 0, headf[MAXE];
int lenb = 0, headb[MAXE];
struct edge {
    int to, next;
    edge() {}
    edge(int To, int Next) {
        to = To;
        next = Next;
    }
} ef[MAXE], eb[MAXN];
void Add_Edge_front(int u, int v) {
    ef[++lenf].to = v;
    ef[lenf].next = headf[u];
    headf[u] = lenf;
}
void Add_Edge_back(int u, int v) {
    eb[++lenb].to = v;
    eb[lenb].next = headb[u];
    headb[u] = lenb;
}

int w[MAXN];
bool visf[MAXN], visb[MAXN];
int ma[MAXN], mi[MAXN], inf[MAXN], inb[MAXN];

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &w[i]);
        mi[i] = ma[i] = w[i];
    }
    for (int i = 1; i <= m; i++) {
        int u, v, flag;
        scanf("%d %d %d", &u, &v, &flag);
        Add_Edge_front(u, v);
        Add_Edge_back(v, u);
        inf[v]++;
        inb[u]++;
        if (flag == 2) {
            Add_Edge_front(v, u);
            Add_Edge_back(u, v);
            inf[u]++;
            inb[v]++;
        }
    }
    queue<int> qf;
    qf.push(1);
    visf[1] = true;
    while (!qf.empty()) {
        int u = qf.front();
        qf.pop();
        for (int i = headf[u]; i; i = ef[i].next) {
            int v = ef[i].to;
            inf[v]--;
            visf[u] = true;
            mi[v] = Min(mi[v], w[u]);
            if (inf[v] == 0)
                qf.push(v);
        }
    }
    queue<int> qb;
    qb.push(n);
    visb[n] = true;
    while (!qb.empty()) {
        int u = qb.front();
        qb.pop();
        for (int i = headb[u]; i; i = eb[i].next) {
            int v = eb[i].to;
            inb[v]--;
            ma[v] = Max(ma[v], w[u]);
            visb[v] = true;
            if (inb[v] == 0)
                qb.push(v);
        }
    }
    int ans = 0;
    for (int i = 1; i <= n; i++)
        if (visb[i] && visf[i])
            ans = Max(ans, ma[i] - mi[i]);
    printf("%d\n", ans);
    return 0;
}

0x03 正解

part1: Tarjan + Topology_Sort

这方面的正解主要是优化之前的拓扑解法。

如何在有环图上跑拓扑?好像不会。但我们会把有环变无环对吧!

于是可以考虑在上述算法前事先 Tarjan 缩点。

当然,本人没调出来。


part2: 类 spfa 解法

事实证明,spfa 可以在有环图上完成部分拓扑排序的工作。

就像 spfa 可以在有环图上完成部分 dijkstra 的工作一样。

对于 spfa, 你会发现,它本质上也是一种根据一定遍历顺序完成图论问题的算法。

也就是说它也可以达到将图拉成类似一条链的结构方便去线性 dp。

具体的,不难看出当且仅当一个点的 \(ma[]\) 或者 \(mi[]\) 发生改变,它才会对后面遍历的点产生影响。

那我们就在每次发生更新之后,让当前结点重新入队即可。

#include <queue>
#include <cstdio>
#include <vector>
using namespace std;

inline int Max(int x, int y) {return x > y ? x : y;}
inline int Min(int x, int y) {return x < y ? x : y;}
const int MAXN = 1e5 + 5;
const int INF = 0x3f3f3f3f;
vector<int> mp1[MAXN], mp2[MAXN];
int w[MAXN];
int mi[MAXN], ma[MAXN];

int main() {
	int n, m;
	scanf ("%d %d", &n, &m);
	for(int i = 1; i <= n; i++) {
		scanf ("%d", &w[i]);
		mi[i] = INF;		
	}
	for(int i = 1; i <= m; i++) {
		int u, v, flag;
		scanf ("%d %d %d", &u, &v, &flag);
		mp1[u].push_back(v);
		mp2[v].push_back(u);
		if(flag == 2) {
			mp1[v].push_back(u);
			mp2[u].push_back(v);
		}
	}
	queue<int> q;
	q.push(1);
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		mi[u] = Min(w[u], mi[u]);
		int len = mp1[u].size();
		for(int i = 0; i < len; i++) {
			int v = mp1[u][i];
			if(w[u] < mi[v]) {
				mi[v] = w[u];
				q.push(v);
			}
		}
	}
	q.push(n);
	while(!q.empty()) {
		int u = q.front();
		q.pop();
		ma[u] = Max(w[u], ma[u]);
		int len = mp2[u].size();
		for(int i = 0; i < len; i++) {
			int v = mp2[u][i];
			if(w[u] > ma[v]) {
				ma[v] = w[u];
				q.push(v);
			}
		}
	}
	int ans = 0;
//	for(int i = 1; i <= n; i++)
//		printf("ma[%d] = %d, mi[%d] = %d\n", i, ma[i], i, mi[i]);
	for(int i = 1; i <= n; i++)
		ans = Max(ans, ma[i] - mi[i]);
	printf("%d\n", ans);
	return 0;
}

part3: 分层图。

来自到机房一位巨佬的启发。

对于每个点有 \(4\) 种状态。

  • 1.之前没买过,当前点买。
  • 2.之前没买过,当前点不买。
  • 3.之前点买过,当前点卖。
  • 4.之前点买过,当前点不卖。

在精简一下:

  • 1.当前点买。
  • 2.当前点卖。

那么根据这些状态我们就可以尝试分层了。

首先原图看做是边权均为 \(0\) 的图。

然后,如果想要到达状态 \(1\) ,则一定通过最初状态。

那我们将原图向图 \(2\) 连条有向边,指向图 \(2\)。这些边的代价为原图上的点的点权的相反数(你买相当于是扣钱嘛。

如果你想到达状态 \(2\),则一定通过状态 \(1\)。你手上必须要有宝石你才能卖a。

于是将图 \(2\) 像图 \(3\) 连条有向边,指向图 \(3\)。这些边的代价为图 \(2\) 所对应的原图上的点的点权。(你又赚回来了。

最后我们规定终点为 \(n * 3 + 1\)。

则原图上的 \(n\) 需要与终点连边(你可以不买也不卖。

图 \(2\) 上的 \(n\) 不需要与终点连边(点权保证为正,所以买了不卖的情况一定不是最优解。

图 \(3\) 上的 \(n\) 需要与终点连边(正常情况对吧。

于是乎。

#include <queue>
#include <cstdio>
#include <cstring>
using namespace std;

const int MAXN = 1e5 + 5;
const int MAXE = 5e5 + 5;
const int INF = 0x3f3f3f3f;

int len = 0, head[MAXN * 3 + 5];
struct edge {
	int to, next, w;
	edge() {}
	edge(int To, int Next, int W) {
		to = To;
		next = Next;
		w = W;
	}
} e[MAXE * 3 + 5];
void Add_Edge(int x, int y, int c) {
	e[++len].to = y;
	e[len].w = c;
	e[len].next = head[x];
	head[x] = len;	
} 

int w[MAXN * 3 + 5], n, m;
void Add_Extra(int x, int y, int c) {
	Add_Edge(x, y, 0);
	Add_Edge(x + n, y + n, 0);
	Add_Edge(x + 2 * n, y + 2 * n, 0);	
	Add_Edge(x, y + n, -c);
	Add_Edge(x + n, y + 2 * n, c);
}

int dist[MAXN * 3 + 5];
bool vis[MAXN * 3 + 5];
void spfa() {
	memset(dist, -INF, sizeof dist);
	queue<int> q;
	vis[1] = true;
	dist[1] = 0;
	q.push(1);
	while(!q.empty()) {
		int u = q.front();
		q.pop();	
		vis[u] = false;
		for(int i = head[u]; i; i = e[i].next) {
			int v = e[i].to, cost = e[i].w;
			if(dist[v] < dist[u] + cost) {
				dist[v] = dist[u] + cost;
				if(!vis[v]) {
					vis[v] = true;
					q.push(v);					
				}
			}
		}
	}
}

int main() {
	scanf ("%d %d", &n, &m);
	for(int i = 1; i <= n; i++) 
		scanf ("%d", &w[i]);
	for(int i = 1; i <= m; i++) {
		int u, v, flag;
		scanf ("%d %d %d", &u, &v, &flag);
		Add_Extra(u, v, w[u]);
		if(flag == 2)
			Add_Extra(v, u, w[v]);		
	}
	Add_Edge(n, n * 3 + 1, 0);
	Add_Edge(n + n * 2, n * 3 + 1, 0);
	n *= 3;
	n++;
	spfa();
	printf("%d\n", dist[n]);
	return 0;
}
上一篇:Day 11.20模拟赛游记


下一篇:数据挖掘实验(一)数据规范化【最小-最大规范化、零-均值规范化、小数定标规范化】