图论——单源最短路的综合应用-EW帮帮网

[CQOI2005] 新年好

重庆城里有 $n$ 个车站， $m$ 条双向公路连接其中的某些车站。每两个车站最多用一条公路连接，从任何一个车站出发都可以经过一条或者多条公路到达其他车站，但不同的路径需要花费的时间可能不同。在一条路径上花费的时间等于路径上所有公路需要的时间之和。

佳佳的家在车站 $1$ ，他有五个亲戚，分别住在车站 $a, b, c, d, e$ 。过年了，他需要从自己的家出发，拜访每个亲戚（顺序任意），给他们送去节日的祝福。怎样走，才需要最少的时间？

输入格式

第一行： $n, m$ ，分别为车站数目和公路的数目。

第二行： $a, b, c, d, e$ ，分别为五个亲戚所在车站编号。

以下 $m$ 行，每行三个整数 $x, y, t$ ，为公路连接的两个车站编号和时间。

输出格式

仅一行，包含一个整数 $T$ ，为最少的总时间。保证 $T\le 10^9$ 。

样例输入 #1

样例输出 #1

对于 $40\%$ 的数据，有 $1 \leq n \leq 500$ ， $1 \leq m \leq 2000$ 。

对于 $100\%$ 的数据，有 $1 \leq n \leq 50000$ ， $1 \leq m \leq 100000$ ， $1\le a,b,c,d,e≤n$ ， $1 \leq x, y \leq n$ ， $1 \leq t \leq 10000$ 。
本题要求的不是单源点最短路，而是从起点开始，走过 $a, b, c, d, e$ 五个点的最短距离。

考虑枚举遍历从1开始走遍 $a, b, c, d, e$ 点的顺序，方案数为 $5!$ ,每一个方案都要走过五条路径，例如方案 $1 - b - a - e - d - c$ 要走过路径 $(1, b), (b, a), (a, e), (e, d), (d, c)$ 。考虑对于每一个方案，都做六遍dijkstra，每次求出来从 $1, a, b, c, d, e$ 中一个点到其他点的最短距离，对于该方案所求的结果就是5个点对之间最短路径的和，这样时间复杂度就是 $O (6! m l o g m)$ 。考虑先求出从这六个点出发到其他点的最短路径，在枚举所有方案，这样就起到了一个预处理的左右，时间复杂度为 $O (6 m l o g m + 5!)$ 。

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;
typedef pair<int,int> PII;
const int N = 50010, M = 1e5 * 2 + 10;
int dist[10][N];
bool st[N];
int h[N], e[M], ne[M], w[M];
int tot;
int source[10];
int n, m;
void add(int a, int b, int c)
{
    e[tot] = b, ne[tot] = h[a], w[tot] = c, h[a] = tot ++ ;
}
void dijkstra(int start, int dist[])
{
    memset(dist, 0x3f, N * 4);
    memset(st, 0, sizeof st);
    dist[start] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    heap.push({dist[start], start});
    while (heap.size())
    {
        auto t = heap.top();
        heap.pop();
        int ver = t.second, distance = t.first;
        if (st[ver]) continue;
        st[ver] = 1;
        for (int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                heap.push({dist[j], j});
            }
        }
    }
    return ;
}
int dfs(int u, int last, int val)
{
    if (u == 6) return val;
    int res = 0x3f3f3f3f;
    for (int i = 2; i <= 6; i ++ )
    {
        int j = source[i];
        if (st[i]) continue;
        st[i] = 1;
        res = min(res, dfs(u + 1, i, val + dist[last][j]));
        st[i] = 0;
    }
    return res;
}
int main()
{
    cin >> n >> m;
    for (int i = 2; i <= 6; i ++ )
        cin >> source[i];
    source[1] = 1;
    memset(h, -1, sizeof h);
    for (int i = 1; i <= m; i ++ )
    {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        add(a, b, c), add(b, a, c);
    }
    for (int i = 1; i <= 6; i ++ )
        dijkstra(source[i], dist[i]);
    memset(st, 0, sizeof st);
    printf("%d\n", dfs(1, 1, 0));
    return 0;
}

通信线路

在郊区有 $N$ 座通信基站， $P$ 条双向电缆，第 $i$ 条电缆连接基站 $A_i$ 和 $B_i$ 。

特别地， $1$ 号基站是通信公司的总站， $N$ 号基站位于一座农场中。
现在，农场主希望对通信线路进行升级，其中升级第 $i$ 条电缆需要花费 $L_i$ 。
电话公司正在举行优惠活动。农产主可以指定一条从 $1$ 号基站到 $N$ 号基站的路径，并指定路径上不超过 $K$ 条电缆，由电话公司免费提供升级服务。
农场主只需要支付在该路径上剩余的电缆中，升级价格最贵的那条电缆的花费即可。

求至少用多少钱可以完成升级。

输入格式
第 $1$ 行：三个整数 $N ， P ， K$ 。

第 $2.. P + 1$ 行：第 $i + 1$ 行包含三个整数 $A_i,B_i,L_i$ 。

输出格式
包含一个整数表示最少花费。

若 $1$ 号基站与 $N$ 号基站之间不存在路径，则输出 −1。

数据范围
$0 \leq K < N \leq 1000, 1 \leq P \leq 10000, 1 \leq L i \leq 1000000$

输入样例：

输出样例：

从1号节点到n号节点之间有若干条路径，本题是要在所有路径里找第 $k + 1$ 大电缆的最小值，因此可以考虑使用二分来做。
可以用二分的情况是所求的答案在某个分界点，具有某个性质，在这个分界点的一边满足这个性质，另一边不满足。

1.对于答案x，需要满足的性质就是从1走到n需要经过大于x的边数小于等于k，作为分界点，此时大于x的边数应该等于k。
2.对于答案右边的区间，x变大了，大于x的边数就会减小，即大于x的边数小于k，同样满足性质；
2.对于答案左边的区间，x变小了，大于x的边数就会增加，即大于x的边数大于k，不满足性质。

接下来需要判断答案x是否满足上面性质。我们把边权大于x的边权置为1，小于等于x的边权置为0，这样一来图就是一个只有0，1边权的图，我们可以求出一条从1到n的最短路径，如果路径长度 $\leq k$ ，则说明x可行。

答案区间为 $[0, 1 e 6 + 1]$ ，取到0则说明存在长度 $\leq k$ 的路径，取到 $1 e 6 + 1$ 则说明不存在通路。

#include <iostream>
#include <cstring>
#include <deque>
using namespace std;
const int N = 1010, M = 200010;
int h[N], e[M], ne[M], w[M];
int tot;
int dist[N];
bool st[N];
int n, p, k;
void add (int a, int b, int c)
{
    e[tot] = b, ne[tot] = h[a], w[tot] = c, h[a] = tot ++ ;
}
bool check(int x)
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    dist[1] = 0;
    deque<int> q;
    q.push_back(1);
    while (q.size())
    {
        int t = q.front();
        q.pop_front();
        if (st[t]) continue;
        st[t] = 1;
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i], val = w[i] > x;
            if (dist[j] > dist[t] + val)
            {
                dist[j] = dist[t] + val;
                if (!val) q.push_front(j);
                else q.push_back(j);
            }
        }
    }
    return dist[n] <= k;
}
int main()
{
    cin >> n >> p >> k;   
    memset(h, -1, sizeof h);
    while (p -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add (a, b, c), add(b, a, c);
    }

    int l = 0, r = 1e6 + 1;
    while (l < r)
    {
        int mid = l + r >> 1;
        if (check(mid)) r = mid;
        else l = mid + 1;
    }
    if (r == 1e6 + 1) r = -1;
    cout << r;
    return 0;
}

道路与航线

农夫约翰正在一个新的销售区域对他的牛奶销售方案进行调查。

他想把牛奶送到 $T$ 个城镇，编号为 $1 \sim T$ 。
这些城镇之间通过 $R$ 条道路 (编号为 $1$ 到 $R$ ) 和 $P$ 条航线 (编号为 $1$ 到 $P$ ) 连接。
每条道路 i或者航线 i连接城镇 $A_i$ 到 $B_i$ ，花费为 $C_i$ 。
对于道路， $0 \leq C i \leq 10, 000$ ;然而航线的花费很神奇，花费 $C i$ 可能是负数 $(- 10, 000 \leq C i \leq 10, 000) 。$
道路是双向的，可以从 $A i$ 到 $B i$ ，也可以从 $B i$ 到 $A i$ ，花费都是 $C i$ 。
然而航线与之不同，只可以从 $A i$ 到 $B i$ 。
事实上，由于最近恐怖主义太嚣张，为了社会和谐，出台了一些政策：保证如果有一条航线可以从 $A i$ 到 $B i$ ，那么保证不可能通过一些道路和航线从 $B i$ 回到 $A i$ 。

由于约翰的奶牛世界公认十分给力，他需要运送奶牛到每一个城镇。

他想找到从发送中心城镇 S把奶牛送到每个城镇的最便宜的方案。

输入格式
第一行包含四个整数 $T, R, P, S$ 。
接下来 $R$ 行，每行包含三个整数（表示一个道路） $A i, B i, C i$ 。
接下来 $P$ 行，每行包含三个整数（表示一条航线） $A i, B i, C i$ 。

输出格式
第 $1.. T$ 行：第 i行输出从 $S$ 到达城镇 $i$ 的最小花费，如果不存在，则输出 NO PATH。

数据范围
$1 \leq T \leq 25000, 1 \leq R, P \leq 50000, 1 \leq A i, B i, S \leq T$

输入样例：

输出样例：

NO PATH
NO PATH
5
0
-95
-100

本题中存在两种路线：
一种是道路，双向，边权非负。
一种是航线，单向，边权可正可负。同时保证保证如果有一条航线可以从 $A_i$ 到 $B_i$ ，那么保证不可能通过一些道路和航线从 $B_i$ 回到 $A_i$ 。
因为含有负边权，不能使用dijkstra，同时一般的spfa又会被卡，考虑把本题抽象为以下模型：
在这里插入图片描述
每一个大圆为一个连通块，大圆内的小圆(城镇)之间可以通过道路相互到达，其中深色小圆为起点，一个大圆可以通过单向的航线到达另一个大圆，大圆之间存在拓扑序。

#include <iostream>
#include <cstring>
#include <queue>
#include <vector>
using namespace std;
typedef pair<int,int> PII;
const int N = 25010, M = 1500010;
int id[N];
int h[N], e[M], ne[M], w[M], tot;
vector<int> block[N];
queue<int> q;
int dist[N];
bool st[N];
int pid;
int din[N];
int n, r, p, s;
void add(int a, int b, int c)
{
    e[tot] = b, ne[tot] = h[a], w[tot] = c, h[a] = tot ++ ;
}
void dfs(int u, int pid)
{
    id[u] = pid;
    block[pid].push_back(u);
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (id[j]) continue;
        dfs(j, pid);
    }
    return ;
}
void dijkstra(int x)
{
    priority_queue<PII, vector<PII>, greater<PII>> heap;
    for (auto i : block[x])
        heap.push({dist[i], i});
    while (heap.size())
    {
        auto t = heap.top();
        int ver = t.second, distance = t.first;
        heap.pop();
        if (st[ver]) continue;
        st[ver] = 1;
        for (int i = h[ver]; ~i; i = ne[i])
        {
            int j = e[i];
            if (dist[j] > dist[ver] + w[i])
            {
                dist[j] = dist[ver] + w[i];
                if (id[j] == id[ver]) heap.push({dist[j], j});
            }
            if (id[j] != id[ver] && (-- din[id[j]]) == 0) q.push(id[j]);
        }
    }
    return ; 
}
void topsort()
{
    memset(dist, 0x3f, sizeof dist);
    dist[s] = 0;
    for (int i = 1; i <= pid; i ++ )
        if (din[i] == 0) q.push(i);
    while (q.size())
    {
        int t = q.front();
        dijkstra(t);
        q.pop();
    }
    return ;
}
int main()
{
    cin >> n >> r >> p >> s;
    memset(h, -1, sizeof h);
    while (r -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c), add(b, a, c);
    }
    for (int i = 1; i <= n; i ++ )
    {
        if (id[i]) continue;
        dfs(i, ++ pid);
    }
    while (p -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
        din[id[b]] ++ ;
    }
    topsort();
    for (int i = 1; i <= n; i ++ )
    {
        if (dist[i] > 0x3f3f3f3f / 2) puts("NO PATH");
        else cout << dist[i] << endl;
    }
    return 0;
}

[NOIP 2009 提高组] 最优贸易

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

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

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

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

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

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

阿龙也可以选择如下一条线路： $1\to4\to5\to4\to5$ ，并在第 $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$ 。

样例输入 #1

样例输出 #1

【数据范围】

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

对于 $10\%$ 的数据， $1\leq n\leq 6$ 。

对于 $30\%$ 的数据， $1\leq n\leq 100$ 。

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

对于 $100\%$ 的数据， $1\leq n\leq 100000$ ， $1\leq m\leq 500000$ ， $1\leq x,y\leq n$ ， $1\leq z\leq 2$ ，$1\leq $ 各城市的编号 $\leq n$ 。

水晶球价格 $\leq 100$ 。

先求出：
从1走到 i的过程中，买入水晶球的最低价格 $d min [i]$ ；
从 i走到n的过程中，卖出水晶球的最高价格 $d ma x [i]$ ；
然后枚举每个城市作为买卖的中间城市，求出 dmax[i] - dmin[i] 的最大值即可。
求 $d min [i]$ 和 $d ma x [i]$ 时，由于不是拓扑图，状态的更新可能存在环，因此不能使用动态规划，只能使用求最短路的方式。
另外，我们考虑能否使用 dijkstra 算法，如果当前 dmin[i] 最小的点是 5，那么有可能存在边 $5 - > 6, 6 - > 7, 7 - > 5$ ，假设当前 $d min [5] = 10$ ，则有可能存在 6 的价格是11，但 7 的价格是3，那么 $d min [5]$ 的值就应该被更新成3，因此当前最小值也不一定是最终最小值，所以dijkstra算法并不适用，我们只能采用 spfa 算法。

#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010, M = 2000010;
int h[N], rh[N], e[M], ne[M];
int val[N];
int tot;
int q[N];
int dist[N];
bool st[N];
int n, m;
int dmin[N], dmax[N];
void add(int h[], int a, int b)
{
    e[tot] = b, ne[tot] = h[a], h[a] = tot ++ ;
}
void spfa(int d[], int start, int h[], bool flag)
{
    memset(st, 0, sizeof st);
    if (!flag) memset(d, 0x3f, sizeof dmin);
    d[start] = val[start];
    int hh = 0, tt = 1;
    q[0] = start;
    st[start] = 1;
    while (hh != tt)
    {
        int t = q[hh ++ ];
        if (hh == N) hh = 0;
        st[t] = 0;
        for (int i = h[t]; ~i; i = ne[i])
        {
            int j = e[i];
            if ((!flag && d[j] > min(d[t], val[j])) || (flag && d[j] < max(d[t], val[j])))
            {
                if (!flag) d[j] = min(d[t], val[j]);
                else d[j] = max(d[t], val[j]);
                if (!st[j])
                {
                    q[tt ++ ] = j;
                    if (tt == N) tt = 0;
                    st[j] = 1;
                }
            }
        }
    }
}
int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i ++ )
        cin >> val[i];
    memset(h, -1, sizeof h);
    memset(rh, -1, sizeof rh);
    while (m -- )
    {
        int a, b, c;
        cin >> a >> b >> c;
        add (h, a, b), add(rh, b, a);
        if (c == 2) add(h, b, a), add(rh, a, b);
    }
    spfa(dmin, 1, h, 0);
    spfa(dmax, n, rh, 1);
    int res = 0;
    for (int i = 1; i <= n; i ++ )
        res = max(res, dmax[i] - dmin[i]);
    cout << res;
    return 0;
}

图论——单源最短路的综合应用

[CQOI2005] 新年好

通信线路

道路与航线

[NOIP 2009 提高组] 最优贸易

网站公告

今日签到

热门文章

最新发布