AcWing图论提高版

最优乘车

1. 建图方式：因为要算的是最少换乘多少次，所以要考虑如何把换乘次数问题转换成最短距离问题。我们可以设置，让一辆车所走的路线之间距离都是1，比如：路线为2 5 7 4，则2->5，2->7，2->4，5->7，5->4，7->4全部设置为1；由此将换乘次数转换成最短路
2. 读入方式：因为读入时的站点数量未知且不唯一，所以利用getline+stringstream进行读入，\(\color{red}{使用getlilne不要忘记读入最开始的换行符}\)

#include <iostream>
#include <sstream>
#include <cstring>
#include <string>
using namespace std;
const int N = 510;
int g[N][N], dist[N];
bool st[N];
int stop[N];
int n, m;
void Dijkstral()
{
    memset(dist, 0x3f, sizeof dist);
    dist[1] = 0;
    for(int i = 0; i < n - 1; i++)
    {
        int t = -1;
        for(int j = 1; j <= n; j++)
        {
            if(!st[j] && (t == -1 || dist[j] < dist[t])) t = j;
        }
        st[t] = true;
        for(int j = 1; j <= n; j++)
        {
            if(dist[j] > dist[t] + g[t][j])
                dist[j] = dist[t] + g[t][j];
        }
    }
}
int main()
{
    memset(g, 0x3f, sizeof g);
    cin >> m >> n;
    string line;
    getline(cin, line);
    while(m--)
    {
        getline(cin, line);
        stringstream ss(line);//不要忘记读\n
        int cnt = 0, p;
        while(ss >> p) stop[cnt++] = p;//因为读入的数量未知，使用stringstream
        for(int i = 0; i < cnt; i++)
            for(int j = i + 1; j < cnt; j++)
                g[stop[i]][stop[j]] = 1;//只要一辆车能走到的地方距离就是1
    }
    Dijkstral();
    if(dist[n] > 0x3f3f3f3f / 2) cout << "NO";
    else cout << dist[n] - 1;
    return 0;
}

昂贵的聘礼

1. 建图方式：将一个物品可以用一个替代品和优惠后的价格购买，转换成一个节点（待购买的物品）由另一个节点（替代品）和指向（待购买物品）的边组成；因为每个物品由有本身的单价，于是创建虚拟原点，指向每个（物品的）节点，边权为物品的单价。
2. 阶级问题：因为该题的数据量较小，可以直接用暴力的方式；我们可以在选择距离最小的点的时候判断level是否符合要求，但这个时候需要注意，如果没有符合要求的点，t可能是-1，导致数组越界，所以需要特判t == -1；也可以在更新距离的时候判断，这时候直接判断即可。
3. 因为重复调用多次Dijsktral，所以需要每次重置st数组

#include <iostream>
#include <cstring>
using namespace std;
const int N = 110;
int g[N][N], dist[N];
bool st[N];
int level[N];
int n, m;
int Dijkstral(int s, int e)
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    dist[0] = 0;
    for (int i = 0; i < n; i++)
    {
        int t = -1;
        for (int j = 0; j <= n; j++)
        {
            if (!st[j] && (level[j] >= s && level[j] <= e) && (t == -1 || dist[j] < dist[t])) t = j;
            //if (!st[j] && (t == -1 || dist[j] < dist[t])) t = j;
        }
        if (t == -1) continue;
        st[t] = true;
        for (int j = 0; j <= n; j++)
        {
            if(level[j] >= s && level[j] <= e)
                dist[j] = min(dist[j], dist[t] + g[t][j]);
        }
    }
    return dist[1];
}
int main()
{
    memset(g, 0x3f, sizeof g);
    for(int i = 0; i <= n; i++) g[i][i] = 0;
    cin >> m >> n;
    for (int i = 1; i <= n; i++)
    {
        int price;
        cin >> price >> level[i];
        g[0][i] = min(g[0][i], price);
        int x;
        cin >> x;
        while (x--)
        {
            int t, v;
            cin >> t >> v;
            g[t][i] = min(g[t][i], v);
        }
    }
    level[0] = level[1];
    int ans = 0x3f3f3f3f;
    for (int i = level[1] - m; i <= level[1]; i++)
    {
        int res = Dijkstral(i, i + m);
        ans = min(ans, res);
    }
    cout << ans;
    return 0;
}

新年好

1. 只要是双向的路径，\(\color{red}{M一定要记得×2！！！！！！！！}\)
2. 因为n的范围比较大，所以不能直接设置\(d[N][N]\)的数组，需要利用映射的方式，让d的第一维从1到6变化
3. 因为一共只有5个亲戚，所以可以直接全排列，使用STL中的next_permutation，在使用前记得排序
4. 以每个亲戚作为原点，计算其他点到该点的距离

#include <bits/stdc++.h>
using namespace std;
const int N = 5e4 + 10, M = (1e5 + 10) * 2;
int head[M], to[M], ne[M], w[M], idx;
int n, m;
int d[10][N];
int source[N];
bool st[N];
int rel[10];
typedef pair<int, int> PII;
priority_queue<PII, vector<PII>, greater<PII>> q;
void Dijkstral(int s, int dist[])
{
    memset(st, 0, sizeof st);
    q.push({ 0, s });
    dist[s] = 0;
    while (q.size())
    {
        auto [d, t] = q.top();
        q.pop();
        if (st[t]) continue;
        st[t] = true;
        for (int i = head[t]; i != -1; i = ne[i])
        {
            int j = to[i];
            if (dist[j] > d + w[i])
            {
                dist[j] = d + w[i];
                q.push({ dist[j], j });
            }
        }
    }
}
void add(int x, int y, int z)
{
    to[idx] = y, ne[idx] = head[x], w[idx] = z, head[x] = idx++;
}
int main()
{
    memset(head, -1, sizeof head);
    memset(d, 0x3f, sizeof d);
    cin >> n >> m;
    rel[0] = 1, source[1] = 0;
    for (int i = 1; i <= 5; i++) cin >> rel[i];
    sort(rel + 1, rel + 6);
    for (int i = 1; i <= 5; i++)  source[rel[i]] = i;
    while (m--)
    {
        int x, y, t;
        cin >> x >> y >> t;
        add(x, y, t); add(y, x, t);
    }
    for (int i = 0; i <= 5; i++) 
        Dijkstral(rel[i], d[i]);
    int ans = 0x3f3f3f3f;
    do
    {
        int res = d[0][rel[1]];
        for (int i = 1; i <= 4; i++) res += d[source[rel[i]]][rel[i + 1]];
        ans = min(ans, res);
    } while (next_permutation(rel + 1, rel + 6));
    cout << ans;
    return 0;
}

通信线路

1. 将题意转换成求：所有线路中，每条线路花费第k+1大的电缆所需要的最小花费
2. 求第k大的最小值/第k小的最大值\(\rightarrow\)利用二分的思想
3. 二分的判断条件：花费大于x的电缆数小于等于k，找满足条件的x的最小值
4. 建图方式：将花费大于x的边权值设置为1，求n号点的最短距离，判断和k比较的大小

#include <bits/stdc++.h>
using namespace std;
const int M = 2e4 + 10, N = 1e3 + 10;
int head[M], to[M], ne[M], w[M], idx;
bool st[N];
int dist[N];
int n, m, k;
typedef pair<int, int> PII;
priority_queue<PII, vector<PII>, greater<PII>> q;
void add(int x, int y, int z)
{
    to[idx] = y, ne[idx] = head[x], w[idx] = z, head[x] = idx++;
}
bool check(int x)
{
    memset(dist, 0x3f, sizeof dist);
    memset(st, 0, sizeof st);
    dist[1] = 0;
    q.push({0, 1});
    while(q.size())
    {
        auto [d, t] = q.top();
        q.pop();
        if(st[t]) continue;
        st[t] = true;
        for(int i = head[t]; ~i; i = ne[i])
        {
            int j = to[i], v = w[i] > x;
            if(dist[j] > d + v)
            {
                dist[j] = d + v;
                q.push({dist[j], j});
            }
        }
    }
    return dist[n] <= k;
}
int main()
{
    memset(head, -1, sizeof head);
    cin >> n >> m >> k;
    while(m--)
    {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
        add(y, x, z);
    }
    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;
}

最优贸易

1. 将问题转换成，求\(1\sim i\)路上水晶球的最小价格、\(i\sim n\)路上水晶球的最大价格，用遍历所有的i，用最大减最小即可
2. 在刚拿到该题的时候，可能会觉得直接用最大价格减最小价格即可，但是因为有的路是单行线，所以有可能不能从最小价格的城市走到最大价格的城市
3. “dp问题都可以转换成最短路径”，那么是用Dijkstral还是spfa呢？Dijsktral的适用条件是，每次堆顶取出的是该点的最小值，但是该图可能存在环，且该图是点的权重不是边的权重，如果有一个环中后面点的权重小于前面点的权重（相当于有负权边），就会导致前一个点第一次出堆时不是该点的最小值，于是Dijsktral不适用；spfa一般情况都适用，于是适用spfa
4. 因为后面是求\(i\sim n\)的最大价格，所以可以反向建图，求i到n的最大价格；只需要多加一个head数组即可

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 1e6 + 10;
int hs[N], he[N], ne[M], to[M], idx;
int price[N];
bool st[N];
int dmin[N], dmax[N];
int n, m;

void add(int h[], int x, int y)
{
    to[idx] = y, ne[idx] = h[x], h[x] = idx++;
}
void spfa(int h[], int s, int d[], int flag)
{
    queue<int> q;
    memset(st, 0, sizeof st);
    if(flag == 0)//求最小值 
        memset(d, 0x3f, sizeof dmin);
    //注意！！！！！！！！不能写sizeof d，因为在函数里面d是一个指针，只占4个字节，而不是d数组的大小
    d[s] = price[s];
    q.push(s);
    st[s] = true;
    while(q.size())
    {
        int t = q.front();
        q.pop();
        st[t] = false;
        
        for(int i = h[t]; ~i; i = ne[i])
        {
            int j = to[i];
            if(flag == 0 && d[j] > min(d[t], price[j]) || flag == 1 && d[j] < max(d[t], price[j]))
            {
                if(flag == 0) d[j] = min(d[t], price[j]);//与求最短路的区别
                else d[j] = max(d[t], price[j]);
                if(!st[j])
                {
                    st[j] = true;
                    q.push(j);
                }
            }
        }
    }
}
int main()
{
    std::ios::sync_with_stdio(0);
    std::cin.tie(0);
    memset(he, -1, sizeof he);
    memset(hs, -1, sizeof hs);
    cin >> n >> m;
    for(int i = 1; i <= n; i++) cin >> price[i];
    while(m--)
    {
        int x, y, z;
        cin >> x >> y >> z;
        add(hs, x, y); add(he, y, x);
        if(z == 2) 
        {
            add(hs, y, x);
            add(he, x, y);
        }
    }
    
    spfa(hs, 1, dmin, 0);
    spfa(he, n, dmax, 1);
    int res = 0;
    for(int i = 1; i <= n; i++) res = max(res, dmax[i] - dmin[i]);
    cout << res;
    return 0;
}

选择最佳路径

在求最短路的过程中，如果题目给出了多个起点

1. 可以用虚拟原点的方式，让虚拟原点到其他的所有起点，这时只需求一次最短路
2. 如果终点只有一个，也可以利用反向建图的方式