DS|图（拓扑排序和最短路径）

题目一：DS图 -- 图的最短路径（无框架）

题目描述：

给出一个图的邻接矩阵，输入顶点v，用迪杰斯特拉算法求顶点v到其它顶点的最短路径。

输入要求：

第一行输入t，表示有t个测试实例

第二行输入顶点数n和n个顶点信息

第三行起，每行输入邻接矩阵的一行，以此类推输入n行

第i个结点与其它结点如果相连则为距离，无连接则为0，数据之间用空格隔开。

第四行输入一个顶点v，表示求该顶点v到其他顶点的最短路径距离

以此类推输入下一个示例

输出要求：

对每组测试数据，输出：

每行输出顶点v到某个顶点的最短距离和最短路径

每行格式：顶点v编号-其他顶点编号-最短路径值----[最短路径]。没有路径输出：顶点v编号-其他顶点编号--1。具体请参考示范数据

输入样例：

2
5 0 1 2 3 4
0 5 0 7 15
0 0 5 0 0
0 0 0 0 1
0 0 2 0 0
0 0 0 0 0
0
6 V0 V1 V2 V3 V4 V5
0 0 10 0 30 100
0 0 5 0 0 0
0 0 0 50 0 0
0 0 0 0 0 10
0 0 0 20 0 60
0 0 0 0 0 0
V0

输出样例：

0-1-5----[0 1 ]
0-2-9----[0 3 2 ]
0-3-7----[0 3 ]
0-4-10----[0 3 2 4 ]
V0-V1--1
V0-V2-10----[V0 V2 ]
V0-V3-50----[V0 V4 V3 ]
V0-V4-30----[V0 V4 ]
V0-V5-60----[V0 V4 V3 V5 ]

代码示例：

#include <iostream>
#include <string>
#include <cstring>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;

class Map {
private:
    int** array;
    string* vertex;
    string start_vertex;
    int n;
    bool visited[50];
    int partnumber;
    int** reach;
    vector<int>* path;
    int* distance;
public:
    Map() {
        cin >> n;
        array = new int* [n];
        reach = new int* [n];
        for (int i = 0; i < n; i++) {
            array[i] = new int[n];
            reach[i] = new int[n];
            for (int j = 0; j < n; j++) array[i][j] = 0, reach[i][j] = 0;
        }
        vertex = new string[n];
        path = new vector<int>[n];
        distance = new int[n];
        for (int i = 0; i < n; i++) vertex[i] = i, distance[i] = 0;
        partnumber = 0;
        memset(visited, false, sizeof(visited));
    }

    int findIndex(string num) {
        for (int i = 0; i < n; i++) if (num == vertex[i]) return i;
        return -1;
    }

    void createMap() {
        int m, v1, v2;
        string num1, num2;
        cin >> m;
        for (int i = 0; i < m; i++) {
            cin >> num1 >> num2;
            v1 = findIndex(num1);
            v2 = findIndex(num2);
            array[v1][v2] = 1, array[v2][v1] = 1;
        }
    }
    void buildMap() {
        for (int i = 0; i < n; i++) cin >> vertex[i];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) cin >> array[i][j];
        }
        cin >> start_vertex;
    }

    void Dijkstra() {
        int startIndex = findIndex(start_vertex);
        for (int i = 0; i < n; i++) {
            if (array[startIndex][i]) {
                distance[i] = array[startIndex][i];
                path[i].push_back(startIndex);
                path[i].push_back(i);
            }
        }
        visited[startIndex] = true;
        for (int i = 0; i < n - 1; i++) {
            int minDistance = 0x3f3f3f;
            int minPosition = 0;
            for (int j = 0; j < n; j++) {
                if (!visited[j] && distance[j] && distance[j] < minDistance) {
                    minPosition = j, minDistance = distance[j];
                }
            }

            visited[minPosition] = true;
            for (int j = 0; j < n; j++)
                if (array[minPosition][j] && !visited[j] && (minDistance + array[minPosition][j] < distance[j] || distance[j] == 0)) {
                    distance[j] = minDistance + array[minPosition][j];
                    path[j] = path[minPosition];
                    path[j].push_back(j);
                }
        }

        for (int i = 0; i < n; i++) {
            if (i == findIndex(start_vertex)) continue;
            if (distance[i]) {
                cout << start_vertex << '-' << vertex[i] << '-' << distance[i] << "----[";
                for (auto& it : path[i]) cout << vertex[it] << ' ';
                cout << "]" << endl;
            }
            else cout << start_vertex << '-' << vertex[i] << "--1" << endl;
        }
    }
    ~Map() {
        for (int i = 0; i < n; i++) delete[]array[i];
        delete[]array;
        delete[]vertex;
    }
};

int main() {
    int t;
    cin >> t;
    while (t--) {
        Map M;
        M.buildMap();
        M.Dijkstra();
    }
}

题目二：DS图 --?拓扑排序

题目描述：

已知有向图，顶点从0开始编号，求它的求拓扑有序序列。

拓扑排序算法：给出有向图邻接矩阵
1.逐列扫描矩阵，找出入度为0且编号最小的顶点v

2.输出v，并标识v已访问

3.把矩阵第v行全清0

重复上述步骤，直到所有顶点输出为止

输入要求：

第一行输入一个整数t，表示有t个有向图

第二行输入n，表示图有n个顶点

第三行起，输入n行整数，表示图对应的邻接矩阵

以此类推输入下一个图的顶点数和邻接矩阵

输出要求：

每行输出一个图的拓扑有序序列

输入样例：

2
5
0 1 0 1 1
0 0 1 0 0
0 0 0 0 1
0 0 1 0 0
0 0 0 0 0
7
0 0 0 0 0 0 0
1 0 1 1 0 0 0
1 0 0 0 0 0 0
1 0 1 0 0 0 0
0 0 0 0 0 1 1
0 1 0 0 0 0 0
0 0 0 1 0 1 0

输出样例：

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

代码示例：

#include <iostream>
using namespace std;

class Map {
private:
    int** array;
    string* vertex;
    string start_vertex;
    int n;
    bool visited[50];
    int partnumber;
    int** reach;
    int origin[20];
    int* indegree;
public:
    Map() {
        cin >> n;
        array = new int* [n];
        reach = new int* [n];
        for (int i = 0; i < n; i++) {
            array[i] = new int[n];
            reach[i] = new int[n];
            for (int j = 0; j < n; j++) array[i][j] = 0, reach[i][j] = 0;
        }
        vertex = new string[n];
        indegree = new int[n];
        for (int i = 0; i < n; i++) vertex[i] = i, indegree[i] = 0;
        partnumber = 0;
        for (int i = 0; i < 50; i++) visited[i] = false;
    }

    int findIndex(string num) {
        for (int i = 0; i < n; i++) if (num == vertex[i]) return i;
        return -1;
    }
    void createMap() {
        int m, v1, v2;
        string num1, num2;
        cin >> m;
        for (int i = 0; i < m; i++) {
            cin >> num1 >> num2;
            v1 = findIndex(num1);
            v2 = findIndex(num2);
            array[v1][v2] = 1, array[v2][v1] = 1;
        }
    }
    void buildMap() {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cin >> array[i][j];
                if (array[i][j]) indegree[j]++;
            }
        }
    }
    void topologySort() {
        int times = n;
        while (times--) {
            for (int i = 0; i < n; i++) {
                if (!indegree[i] && !visited[i]) {
                    cout << i << ' ';
                    visited[i] = true;;
                    for (int j = 0; j < n; j++) {
                        if (array[i][j] != 0) indegree[j]--, array[i][j] = 0;
                    }
                    break;
                }
            }
        }
        cout << endl;
    }
    void printMap() {
        for (int i = 0; i < n; i++) {
            cout << vertex[i];
            if (i == n - 1) cout << endl;
            else cout << " ";
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                cout << array[i][j];
                if (j == n - 1) cout << endl;
                else cout << " ";
            }
        }
    }
    ~Map() {
        for (int i = 0; i < n; i++) delete[]array[i];
        delete[]array;
        delete[]vertex;
    }
};

int main() {
    int t;
    cin >> t;
    while (t--) {
        Map M;
        M.buildMap();
        M.topologySort();
    }
}

题目三：DS图 -- 货币套汇（图路径）

题目描述：

套汇是指利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种货币。例如，假定1 美元可以买0.7 英镑，1 英镑可以买9.5 法郎，1法郎可以买到0.16美元。通过货币兑换，一个商人可以从1 美元开始买入，得到0.7×9.5×0.16=1.064美元，从而获得6.4%的利润。 给定n种货币c1 ,c2 ,... ,cn的有关兑换率，试设计一个有效算法，确定货币间是否存在套汇的可能性。

提示：判断图上是否出现正环,即环上所有的边相乘大于1

输入要求：

第一行：测试数据组数

每组测试数据格式为：

第一行：正整数n (1< =n< =30)，正整数m，分别表示n种货币和m种不同的货币兑换率。

2~n+1行，n种货币的名称。

n+2~n+m+1行，每行有3 个数据项ci，rij 和cj ，表示货币ci 和cj的兑换率为 rij。

输出要求：

对每组测试数据，如果存在套汇的可能则输出YES

如果不存在套汇的可能，则输出NO。

输入样例：

2
3 3
USDollar
BritishPound
FrenchFranc
USDollar 0.5 BritishPound
BritishPound 10.0 FrenchFranc
FrenchFranc 0.21 USDollar
3 6
USDollar
BritishPound
FrenchFranc
USDollar 0.5 BritishPound
USDollar 4.9 FrenchFranc
BritishPound 10.0 FrenchFranc
BritishPound 1.99 USDollar
FrenchFranc 0.09 BritishPound
FrenchFranc 0.19 USDollar

输出样例：

YES
NO

代码示例：

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

class Map {
private:
    double** array;
    string* vertex;
    string start_vertex;
    int n;
    int m;
    bool visited[50];
    int partnumber;
    int** reach;
    int origin[20];
    int* indegree;
public:
    Map() {
        cin >> n >> m;
        array = new double* [n];
        reach = new int* [n];
        for (int i = 0; i < n; i++) {
            array[i] = new double[n];
            reach[i] = new int[n];
            for (int j = 0; j < n; j++) array[i][j] = 0, reach[i][j] = 0;
        }
        vertex = new string[n];
        indegree = new int[n];
        for (int i = 0; i < n; i++) cin >> vertex[i], indegree[i] = 0;
        partnumber = 0;
        for (int i = 0; i < 50; i++) visited[i] = false;
    }
    int findIndex(string num) {
        for (int i = 0; i < n; i++) if (num == vertex[i]) return i;
        return -1;
    }
    void createMap() {
        int v1, v2;
        double er;
        string num1, num2;
        for (int i = 0; i < m; i++) {
            cin >> num1 >> er >> num2;
            v1 = findIndex(num1);
            v2 = findIndex(num2);
            array[v1][v2] = er;
        }
    }
    void Arbitrage() {
        for (int i = 0; i < n; i++) {
            queue<string> q;
            q.push(vertex[i]);
            int head = i;
            for (int k = 0; k < n; k++) {
                for (int j = 0; j < n; j++) {
                    if (vertex[j] == q.front()) {
                        q.push(vertex[j]);
                        double sum = 1;
                        while (q.size() > 1) {
                            int x = findIndex(q.front());
                            q.pop();
                            int y = findIndex(q.front());
                            sum *= array[x][y];
                        }
                        if (sum > 1) {
                            cout << "YES" << endl;
                            return;
                        }
                    }
                    else if (array[head][j]) {
                        q.push(vertex[j]);
                        head = j;
                        continue;
                    }
                }
            }
        }
        cout << "NO" << endl;
    }
    ~Map() {
        for (int i = 0; i < n; i++) delete[]array[i];
        delete[]array;
        delete[]vertex;
    }
};

int main() {
    int t;
    cin >> t;
    while (t--) {
        Map M;
        M.createMap();
        M.Arbitrage();
    }
}

题目四：DS图 --?关键路径-STL版

题目描述：

给定有向图无环的边信息，求每个顶点的最早开始时间、最迟开始时间。

输入要求：

第一行图的顶点总数

第二行边的总数

第三行开始，每条边的时间长度，格式为源结点?? 目的结点?? 长度

输出要求：

第一行：第个顶点的最早开始时间

第二行：每个顶点的最迟开始时间

输入样例：

9
12
0 1 3
0 2 10
1 3 9
1 4 13
2 4 12
2 5 7
3 6 8
3 7 4
4 7 6
5 7 11
6 8 2
7 8 5

输出样例：

0 3 10 12 22 17 20 28 33 
0 9 10 23 22 17 31 28 33 

代码示例：

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

const int MAX_NODES = 1e5 + 20;
int num_nodes, num_edges, in_degree[MAX_NODES], order_count, top_order[MAX_NODES];
vector<int> adjacency[MAX_NODES], weights[MAX_NODES];
int earliest_completion[MAX_NODES], latest_completion[MAX_NODES];

void topological_sort() {
    queue<int> q;
    for (int i = 0; i < num_nodes; i++) {
        if (in_degree[i] == 0) q.push(i);
    }
    while (!q.empty()) {
        int current_node = q.front();
        q.pop();
        top_order[++order_count] = current_node;
        for (int i = 0; i < adjacency[current_node].size(); i++) {
            int neighbor = adjacency[current_node][i];
            if (--in_degree[neighbor] == 0) q.push(neighbor);
        }
    }
}

int main() {
    cin >> num_nodes >> num_edges;
    while (num_edges--) {
        int from, to, weight;
        cin >> from >> to >> weight;
        adjacency[from].push_back(to);
        in_degree[to]++;
        weights[from].push_back(weight);
    }
    topological_sort();
    for (int k = 1; k <= order_count; k++) {
        int current_node = top_order[k];
        for (int i = 0; i < adjacency[current_node].size(); i++) {
            int neighbor = adjacency[current_node][i], edge_weight = weights[current_node][i];
            earliest_completion[neighbor] = max(earliest_completion[neighbor], earliest_completion[current_node] + edge_weight);
        }
    }
    for (int i = 0; i < num_nodes; i++) {
        cout << earliest_completion[i] << " ";
        latest_completion[i] = earliest_completion[top_order[order_count]];
    }
    cout << endl;
    for (int v = order_count; v >= 1; v--) {
        int current_node = top_order[v];
        for (int i = 0; i < adjacency[current_node].size(); i++) {
            int neighbor = adjacency[current_node][i], edge_weight = weights[current_node][i];
            latest_completion[current_node] = min(latest_completion[current_node], latest_completion[neighbor] - edge_weight);
        }
    }
    for (int i = 0; i < num_nodes; i++) {
        cout << latest_completion[i] << " ";
    }
    return 0;
}

题目五：DS图 -- 旅游规划

题目描述：

有了一张自驾旅游路线图，你会知道城市间的高速公路长度、以及该公路要收取的过路费。现在需要你写一个程序，帮助前来咨询的游客找一条出发地和目的地之间的最短路径。如果有若干条路径都是最短的，那么需要输出最便宜的一条路径。

输入要求：

输入数据的第1行给出4个正整数N、M、S、D，其中N（2≤N≤500）是城市的个数，顺便假设城市的编号为0~(N?1)；M是高速公路的条数；S是出发地的城市编号；D是目的地的城市编号。随后的M行中，每行给出一条高速公路的信息，分别是：城市1、城市2、高速公路长度、收费额，中间用空格分开，数字均为整数且不超过500。输入保证解的存在。

输出要求：

在一行里输出路径的长度和收费总额，数字间以空格分隔，输出结尾不能有多余空格。

输入样例：

4 5 0 3
0 1 1 20
1 3 2 30
0 3 4 10
0 2 2 20
2 3 1 20

输出样例：

3 40

代码示例：

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

class Map {
private:
    int** array;
    int** fee;
    string* vertex;
    string start_vertex, end_vertex;
    int n;
    int m;
    bool visited[50];
    int partnumber;
    int** reach;
    int origin[20];
    int* indegree;
public:
    Map() {
        cin >> n >> m >> start_vertex >> end_vertex;
        array = new int* [n];
        fee = new int* [n];
        reach = new int* [n];
        for (int i = 0; i < n; i++) {
            array[i] = new int[n];
            fee[i] = new int[n];
            reach[i] = new int[n];
            for (int j = 0; j < n; j++) array[i][j] = 0x3f3f3f, fee[i][j] = 0x3f3f3f, reach[i][j] = 0;
        }
        vertex = new string[n];
        indegree = new int[n];
        for (int i = 0; i < n; i++) vertex[i] = i + '0', indegree[i] = 0;
        partnumber = 0;
        for (int i = 0; i < 50; i++) visited[i] = false;
    }
    int findIndex(string num) {
        for (int i = 0; i < n; i++) if (num == vertex[i]) return i;
        return -1;
    }
    void createMap() {
        int v1, v2;
        int dis, cost;
        string num1, num2;
        for (int i = 0; i < m; i++) {
            cin >> num1 >> num2 >> dis >> cost;
            v1 = findIndex(num1);
            v2 = findIndex(num2);
            array[v1][v2] = dis, fee[v1][v2] = cost;
        }
    }
    void Floyd() {
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (array[i][j] > array[i][k] + array[k][j]) {
                        array[i][j] = array[i][k] + array[k][j];
                        fee[i][j] = fee[i][k] + fee[k][j];
                    }
                    else if (array[i][j] == array[i][k] + array[k][j]) {
                        fee[i][j] = min(fee[i][j], fee[i][k] + fee[k][j]);
                    }
                }
            }
        }
        cout << array[findIndex(start_vertex)][findIndex(end_vertex)] << " " << fee[findIndex(start_vertex)][findIndex(end_vertex)] << endl;
    }
    ~Map() {
        for (int i = 0; i < n; i++) delete[]array[i];
        delete[]array;
        delete[]vertex;
    }
};

int main() {
    Map M;
    M.createMap();
    M.Floyd();
}

题目六：DS图 --?拯救007

题目描述：

在老电影“007之生死关头”（Live and Let Die）中有一个情节，007被毒贩抓到一个鳄鱼池中心的小岛上，他用了一种极为大胆的方法逃脱 —— 直接踩着池子里一系列鳄鱼的大脑袋跳上岸去！（据说当年替身演员被最后一条鳄鱼咬住了脚，幸好穿的是特别加厚的靴子才逃过一劫。）

设鳄鱼池是长宽为100米的方形，中心坐标为 (0, 0)，且东北角坐标为 (50, 50)。池心岛是以 (0, 0) 为圆心、直径15米的圆。给定池中分布的鳄鱼的坐标、以及007一次能跳跃的最大距离，你需要告诉他是否有可能逃出生天。

输入要求：

首先第一行给出两个正整数：鳄鱼数量?N（≤100）和007一次能跳跃的最大距离?D。随后?N?行，每行给出一条鳄鱼的?(x,y)?坐标。注意：不会有两条鳄鱼待在同一个点上。

输出要求：

如果007有可能逃脱，就在一行中输出"Yes"，否则输出"No"。

输入样例：

14 20
25 -15
-25 28
8 49
29 15
-35 -2
5 28
27 -29
-8 -28
-20 -35
-25 -20
-13 29
-30 15
-35 40
12 12

输出样例：

Yes

代码示例：

#include <iostream>
#include <cmath>
#include <queue>

using namespace std;
int N;
double D;
bool visited[100];
struct point {
    double x, y;
} points[105];

bool BFS(int n) {
    queue<int> q;
    for (int i = 0; i < 100; ++i) visited[i] = false;
    q.push(n);
    visited[n] = true;
    while (!q.empty()) {
        int f = q.front();
        q.pop();
        if (50 - fabs(points[f].x) <= D || 50 - fabs(points[f].y) <= D) return true;
        for (int i = 0; i < N; ++i) {
            if (!visited[i] && (points[f].x - points[i].x) * ((points[f].x - points[i].x)) + (points[f].y - points[i].y) * (points[f].y - points[i].y) <= D * D) {
                q.push(i);
                visited[i] = true;
            }
        }
    }
    return false;
}

int main() {
    cin >>  N >> D;
    double x, y;
    for (int i = 0; i < N; ++i) {
        cin >> x >> y;
        points[i] = { x, y };
    }
    if (D >= 50 - 7.5) {
        cout << "Yes" << endl;
        return 0;
    }
    for (int i = 0; i < N; ++i) {
        if ((D + 7.5) * (D + 7.5) >= points[i].x * points[i].x + points[i].y * points[i].y) {
            if (BFS(i)) {
                cout << "Yes" << endl;
                return 0;
            }
        }
    }
    cout << "No" << endl;
    return 0;
}