最新要闻

广告

手机

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

iphone11大小尺寸是多少?苹果iPhone11和iPhone13的区别是什么?

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

警方通报辅警执法直播中被撞飞:犯罪嫌疑人已投案

家电

微头条丨AcWing341. 洛谷P1073, NOIP2009 最优贸易

来源:博客园


(资料图片)

AcWing题目传送门洛谷题目传送门

题目大意

\(~~~~~~\)一个投机倒把的奸商想要通过城市不太健全的贸易系统坑点钱,任意城市都可以买入或者卖出水晶球,他想尽量在便宜的城市买入,在贵的城市卖出,以此赚取更高的差价,他必须从一号城市开始旅行,到\(n\)号城市结束。请问他最多可以赚多少钱?

解题思路

\(~~~~~~\)这题乍一看貌似是毫无头绪的,但是我们可以通过差价高推出,他应该价格尽量低买入,价格尽量高的卖出,所以我们可以在从\(1\sim n\) 的路径中选择一个分界点,记作\(k\),这个\(k\)点的含义就是奸商决定在\(1\sim k\)的城市中买入,\(k\sim n\)中的城市卖出,基于我们的买入尽量低,卖出尽量高原则,我们可以得到我们的基本思路:

\(~~~~~~\)枚举所有的\(k\)点,找出\(1\sim k\)中需要的价格最小的点(有路径可以到达的),用\(dmin\)数组记录, 再找出\(k\sim n\)中需要的价格最大的点(存在到\(n\)的路径的),用\(dmax\)数组记录,最后统计答案时找出\(dmax_{i}-dmin_{i}\) 的值最大的点

具体实现

\(~~~~~~\)怎么找出\(1\sim k\)中的最小点呢,难道是枚举每条\(a_{i}\sim k(\forall a_{i}\in [1,k])\)的路中最便宜的点吗?这样未免也太慢了。我们可以采用\(SPFA\)算法,枚举从\(1\)开始的单源最短路(这里最短路的松弛操作需要略做改动),这样对于\(\forall k\in [1,n]\),所有的最短距离都计算好了。

对于\(k\sim n\)的最大点我们也采用类似以上的做法:\(~~~~~~\)我们枚举从\(k\)开始的最短路,松弛操作同样改动,那我们就可以算出\(\forall k\in [1,n]\)到\(n\)点的最大价值了。但是这样需要做\(n\)遍\(SPFA\),一定是不能再时间上通过的,所以该算法应该经过一点改进。

\(~~~~~~\)经过观察可以发现所有的汇点都是\(n\),我们就可以自然地建一个反图(将所有的边方向反转),这样子反图上跑出来的以\(n\)为源点的最长路,就是原图上各点到\(n\)的最长路了。

对于代码

\(~~~~~~~~~~~~~~~~~~~~~~~~\)我们可以写两个\(SPFA\),一个求最短路,一个求最长路\(~~~~~~~~~~~~~~~~~~~~~~~~\)也可以合并处理,这里两份代码都放上来了

代码

两个\(SPFA\)

#include #include #include using namespace std;const int N = 3e5 + 10, M = 2e6 + 10, INF = 0x3f3f3f3f;int dmax[N], dmin[N], st[N];int h[N], rh[N], e[M], ne[M], w[N], idx;int n, m;void add(int *h, int a, int b) {    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;}void spfa() {    queue q;    memset(st, 0, sizeof st);    memset(dmin, 0x3f, sizeof dmin);        dmin[1] = w[1], st[1] = true, q.push(1);        while (q.size())     {        auto t = q.front(); q.pop();        st[t] = false ;                for (int i = h[t]; ~i; i = ne[i])         {            int j = e[i];            if (dmin[j] > min(dmin[t], w[j]))             {                dmin[j] = min(dmin[t], w[j]);                if (!st[j]) st[j] = true, q.push(j);            }        }    }}void rspfa() {    queue q;    memset(st, 0, sizeof st);    memset(dmax, 0xcf, sizeof dmax);        dmax[n] = w[n], st[n] = true, q.push(n);        while (q.size())     {        auto t = q.front(); q.pop();        st[t] = false ;                for (int i = rh[t]; ~i; i = ne[i])         {            int j = e[i];            if (dmax[j] < max(dmax[i], w[j]))             {                dmax[j] = max(dmax[i], w[j]);                if (!st[j]) q.push(j);            }        }    }}int main() {    scanf("%d%d", &n, &m);        for (int i = 1; i <= n; i ++ )         scanf("%d", &w[i]);            memset(h, -1, sizeof h);    memset(rh, -1, sizeof rh);        while (m -- )     {        int u, v, t;        scanf("%d%d%d", &u, &v, &t);        add(h, u, v), add(rh, v, u);        if (t == 2) add(h, v, u), add(rh, u, v);    }        spfa(), rspfa();         int res = 0;    for (int i = 1; i <= n; i ++ )         res = max(res, dmax[i] - dmin[i]);    printf("%d\n", res);        return 0;}

观察到我们写的两个\(SPFA\)其实有很多相似点,所以可以合并成一个,加上一些参数就行(用来区分, 例如:遍历的邻接表不同,起点不同,要求的最短和最长性质不同)但是在合并的\(SPFA\)中要注意:\(memset\)的时候因为我们传进去的距离数组只是一个指针,所以与我们要的字节大小不符合,所以应该写成memset(d, 0x3f, sizeof dmin);当然这只是示例\(合并的SPFA\)

#include #include #include using namespace std;const int N = 2e5 + 10, M = 1e6 + 10, INF = 0x3f3f3f3f;int dmax[N], dmin[N], st[N];int h[N], rh[N], e[M], ne[M], w[N], idx;int n, m;void add(int *h, int a, int b) {    e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;}void spfa(int *h, int *d, int S, int type) {    memset(st, 0, sizeof st);    if (type) memset(d, 0xcf, sizeof dmax);    else memset(d, 0x3f, sizeof dmin);        queue q;    d[S] = w[S], q.push(S), st[S] = true;        while (q.size())     {        auto t = q.front(); q.pop();        st[t] = false ;                for (int i = h[t]; ~i; i = ne[i])         {            int j = e[i];            if (type) {                if (d[j] < max(d[t], w[j]))                 {                    d[j] = max(d[t], w[j]);                    if (!st[j]) q.push(j);                }            }            else {                if (d[j] > min(d[t], w[j]))                 {                    d[j] = min(d[t], w[j]);                    if (!st[j]) q.push(j);                }            }        }    }}int main() {    scanf("%d%d", &n, &m);        for (int i = 1; i <= n; i ++ )         scanf("%d", &w[i]);            memset(h, -1, sizeof h);    memset(rh, -1, sizeof rh);        while (m -- )     {        int u, v, t;        scanf("%d%d%d", &u, &v, &t);        add(h, u, v), add(rh, v, u);        if (t == 2) add(h, v, u), add(rh, u, v);    }        spfa(h, dmin, 1, 0); // 正着跑最短路    spfa(rh, dmax, n, 1); // 反着跑最长路        int res = 0;    for (int i = 1; i <= n; i ++ )         res = max(res, dmax[i] - dmin[i]);    printf("%d\n", res);        return 0;}

写法对比

两个\(SPFA\):时间\(250ms\),码量\(94\)行,容易\(Debug\)(原因:分开逻辑清晰一点)一个\(SPFA\):时间\(227ms\),码量\(80\)行,容易出\(Bug\),不好\(Debug\)(原因:我菜)

\(\color{Green}{Accepted!}\)

关键词: 毫无头绪 最短距离 因为我们