数据结构OJ实验11-拓扑排序与最短路径

A. DS图—图的最短路径（无框架）

题目描述

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

输入

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

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

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

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

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

以此类推输入下一个示例

输出

对每组测试数据，输出：

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

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

样例查看模式?

正常显示查看格式

输入样例1?

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

输出样例1

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

AC代码

#include<bits/stdc++.h>
using namespace std;
const int inf = 0x3f3f3f3f;
vector<vector<int>>a(5);
class Graph
{
    int n;
    vector<string>v;
    vector<vector<int>>adj;
    vector<string>path;
    vector<int>d;
    string start;
public:
    Graph()
    {
        cin >> n;
        path.resize(n);
        d.resize(n);
        for (int i = 0; i < n; i++)
        {
            string x;
            cin >> x;
            v.push_back(x);
        }
        adj.resize(n);
        for (int i = 0; i < n; i++)
        {
            adj[i].resize(n);
        }
        for (int i = 0; i < n; i++)
        {
            for (int j = 0; j < n; j++)
            {
                cin >> adj[i][j];
                if (adj[i][j] == 0)
                {
                    adj[i][j] = inf;
                }
            }
        }
        cin >> start;
    }
    void shortpacth()
    {
        int sv, cur, mind;
        vector<bool>final;
        final.resize(n);
        for (int i = 0; i < n; i++)
        {
            if (v[i] == start)
            {
                sv = i;
                break;
            }
        }
        for (int i = 0; i < n; i++)
        {
            path[i].append(start + " ");
            d[i] = inf;
            if (adj[sv][i] < inf)
            {
                d[i] = adj[sv][i];
                path[i].append(v[i] + " ");
            }
            final[i] = 0;
        }
        d[sv] = 0;
        final[sv] = 1;
        for (int i = 0; i < n - 1; i++)
        {
            mind = inf;
            for (int j = 0; j < n; j++)
            {
                if (!final[j])
                {
                    if (d[j] < mind)
                    {
                        cur = j;
                        mind = d[j];
                    }
                }
            }
            final[cur] = 1;
            for (int j = 0; j < n; j++)
            {
                if (!final[j] && (mind + adj[cur][j] < d[j]))
                {
                    d[j] = mind + adj[cur][j];
                    path[j] = path[cur];
                    path[j].append(v[j] + " ");
                }
            }
        }
    }
    void print()
    {
        for (int i = 0; i < n; i++)
        {
            if (!d[i])continue;
            if (d[i] == inf)
                cout << start << "-" << v[i] << "--1" << endl;
            else
                cout << start << "-" << v[i] << "-" << d[i] << "----[" << path[i] << "]" << endl;
        }
    }
};
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        Graph g;
        g.shortpacth();
        g.print();
    }
    return 0;
}

B. 图综合练习--拓扑排序

题目描述

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

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

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

3.把矩阵第v行全清0

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

--程序要求--

若使用C++只能include一个头文件iostream；若使用C语言只能include一个头文件stdio

程序中若include多过一个头文件，不看代码，作0分处理

不允许使用第三方对象或函数实现本题的要求

输入

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

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

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

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

输出

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

样例查看模式?

正常显示查看格式

输入样例1?

2\n
5\n
0?1?0?1?1\n
0?0?1?0?0\n
0?0?0?0?1\n
0?0?1?0?0\n
0?0?0?0?0\n
7\n
0?0?0?0?0?0?0\n
1?0?1?1?0?0?0\n
1?0?0?0?0?0?0\n
1?0?1?0?0?0?0\n
0?0?0?0?0?1?1\n
0?1?0?0?0?0?0\n
0?0?0?1?0?1?0\n

输出样例1

0?1?3?2?4?\n
4?6?5?1?3?2?0?\n

AC代码

#include<iostream>
using namespace std;
class graph
{
    int **adj;
    int n;
public:
    graph()
    {
        cin>>n;
        adj = new int* [n];
        for(int i=0;i<n;i++)
        {
            adj[i]=new int [n]; 
            for(int j=0;j<n;j++)
            {
                cin>>adj[i][j];
            }
        }
    }
    ~graph()
    {
        for(int i=0;i<n;i++)
        {
            delete[]adj[i];
        }
        delete[]adj;
    }
    bool check(int x)//入度为0
    {
        for(int i=0;i<n;i++)
        {
            if(adj[i][x])return 0;
        }
        return 1;
    }
    void torpot()
    {
        bool *visit;
        visit = new bool[n]{0};//为0
        int res=n;
        while(res--)
        {
            for(int i=0;i<n;i++)
            {
                if(!visit[i]&&check(i))
                {
                    cout<<i<<" ";
                    visit[i]=1;
                    //更新
                    for(int j=0;j<n;j++)
                    {
                        adj[i][j]=0;
                    }
                    break;
                }
            }
        }
        cout<<endl;
        delete[]visit;
    }
};
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        graph g;
        g.torpot();
    }
    return 0;
}

C. 货币套汇（图路径）

题目描述

套汇是指利用货币汇兑率的差异将一个单位的某种货币转换为大于一个单位的同种货币。例如，假定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。

样例查看模式?

正常显示查看格式

输入样例1?

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

输出样例1

YES\n
NO

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=50;
map<string,int>mp;
double a[N][N];
int n,m;
void floy()
{
    for(int k=0;k<n;k++)
    {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
               a[i][j]=max(a[i][j],a[i][k]*a[k][j]);
            }
        }
    }
    //判断是否存在正环
    for(int i=0;i<n;i++)
    {
        if(a[i][i]>1)
        {
            cout<<"YES"<<endl;
            return;
        }
    }
    cout<<"NO"<<endl;
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        memset(a,0,sizeof(a));
        cin>>n>>m;
        for(int i=0;i<n;i++)
        {
            string x;
            cin>>x;
            mp[x]=i;
            a[i][i]=1;//本身自己与自己的环
        }
        for(int i=0;i<m;i++)
        {
            string s1,s2;
            double c;
            cin>>s1>>c>>s2;
            a[mp[s1]][mp[s2]]=c;
        }
        floy();
    }
    return 0;
}

D. 关键路径-STL版

题目描述

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

// 参考代码

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

class Vertex {
public:
    int indexNo;
    bool hasEnterQueue;
    int early;
    int later;

    Vertex(int indexNo) {
        this->indexNo = indexNo;
        this->hasEnterQueue = false;
        early = -1;
        later = 0x7FFFF;
    }
    void updateEarly(int parentEarly, int edgeValue) {
        int newEarly = parentEarly + edgeValue;
        if (newEarly > this->early)
            this->early = newEarly;
    }
    void updateLater(int childLater, int edgeValue) {
        int newLater = childLater - edgeValue;
        if (newLater < this->later)
            this->later = newLater;
    }
};


class Graph {
public:
    vector<Vertex> vertexes;
    vector<vector<int> > adjMat;
    int n;
public:
    void readVertexes() {
        //TODO: 将顶点数读入成员变量n
        
        //TODO： 从输入初始化vertexes数组
        int i=0;
        for(; i<n; ++i) {
            Vertex v(i);
            this->vertexes.push_back(v);
        }
        
        //为成员变量adjMat创建内存，赋初值
        for(i=0; i<n; ++i) {
            vector<int> row;
            int j=0;
            for(; j<n; ++j) {
                //TODO： 将0增加到row最后
            }
           //TODO： 将row增加到adjMat最后
        }
    }
    void readAdjMatrix() {
        //read the adjacent info into this->adjMat
        int edges;
        cin >> edges;
        int i=0;
        int s, t, w;  //s源顶点编号，t目的顶点编号，w边长
        for(; i<edges; ++i) {
            //TODO: 读入s,t,w，并将adjMat的第s行、第t列的值改为w.
        }
    }

    void updateEarly(int parentNo, queue<int>& earlyQue) {
        int parentEarly = vertexes[parentNo].early;  //读入父结点early值

        int j=0;
        for(; j<n; ++j) {
            int edgeValue = adjMat[parentNo][j];
            if (edgeValue == 0) continue;  //若父结点与结点j没有边相连，pass

            Vertex& child = vertexes[j];
            child.updateEarly(parentEarly, edgeValue); //更新子结点j的early信息

            if(!child.hasEnterQueue) {
                child.hasEnterQueue = true; //将子结点加入队列
                earlyQue.push(j);
            }
        }
    }
    void updateLater(int childNo, queue<int>& laterQue) {
        //TODO:
    }

    int getRoot() {
        //获取入度为0的顶点
        int j=0;
        for(; j<n; ++j) {
            int i=0;
            for(; i<n && adjMat[i][j] == 0; ++i);
            if (i>=n) return j; //j has not any in-edges.
        }
        return -1;  //表示没找到
    }
    int getLeaf() {
        //TODO： 获取出度为0的顶点
    }

    void printEarlyLater(bool isEarly) {
        int i=0;
        for(; i<n; ++i) {
            Vertex& v = vertexes[i];
            if (isEarly)
                cout << v.early << " ";
            else {
                cout << v.later << " ";
            }
        }
        cout << endl;
    }

    void findEarly() {
        //执行关键路径算法，求每个顶点的最早开始时间。
        int r = getRoot();
        Vertex& root = vertexes[r];
        root.hasEnterQueue = true;
        root.early = 0;

        queue<int> que;
        que.push(r);

        while(!que.empty()) {
            int p = que.front();
            que.pop();

            updateEarly(p, que);
        }

        printEarlyLater(true);
    }
    void clearEnterQueue() {
        int i=0;
        for(; i<n; ++i) {
            vertexes[i].hasEnterQueue = false;
        }
    }
    void findLater() {
        //TODO：调用clearEnterQueue，以清除每个顶点的hasEnterQueue=false
        //执行关键路径算法，求每个顶点的最迟开始时间。
    }

    void main() {
        readVertexes();
        readAdjMatrix();
        findEarly();
        findLater();
    }
};


int main() {
    int t=1;
    //cin >> t;
    while (t--) {
        Graph g;
        g.main();
    }
    return 0;
}

输入

第一行图的顶点总数

第二行边的总数

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

输出

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

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

样例查看模式?

正常显示查看格式

输入样例1?

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

输出样例1

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

AC代码

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
const int N = 100000;
int n, m;
int in[N], early[N], later[N], top[N];
vector<int>edge[N];//邻接表
vector<int>value[N];//记录权值
int cnt;
void topsort()
{
    queue<int>q;
    for (int i = 0; i < n; i++)
    {
        if (in[i] == 0)q.push(i);//入度为0
    }
    while (!q.empty())
    {
        int cur = q.front();
        q.pop();
        top[++cnt] = cur;
        //断开相邻边
        for (int i = 0; i < edge[cur].size(); i++)
        {
            int j = edge[cur][i];
            --in[j];
            if (in[j] == 0)
            {
                q.push(j);
            }
        }
    }
}
//只有按照拓扑序才能保证顶点的最晚和最早发生时间
void calEarlylater()
{
    //枚举拓扑序
    for (int i = 1; i <= cnt; i++)
    {
        int tt = top[i];
        for (int j = 0; j < edge[tt].size(); j++)
        {
            int ee = edge[tt][j], w = value[tt][j];
            early[ee] = max(early[ee], early[tt] + w);
            //终点的最早发生时间（与起点最早发生时间+dur)取最大值
        }
    }
    for (int i = 0; i < n; i++)
    {
        cout << early[i] << " ";
        later[i] = early[top[cnt]];//每个顶点的最晚发生时间初始为拓扑序列最后一个顶点的最早发生时间
    }
    cout << endl;
    //拓扑序逆着求最晚发生时间
    for (int i = cnt; i >= 1; i--)
    {
        int tt = top[i];
        for (int j = 0; j < edge[tt].size(); j++)
        {
            int ee = edge[tt][j], w = value[tt][j];
            later[tt] = min(later[tt], later[ee] - w);
            //最晚发生时间求最小值
            //(大家都想晚点开始早点结束)
        }
    }
    for (int i = 0; i < n; i++)
    {
        cout << later[i] << " ";
    }
    cout << endl;
}
int main()
{
    cin >> n >> m;
    while (m--)
    {
        int s, t, w;
        cin >> s >> t >> w;
        edge[s].push_back(t);
        in[t]++;
        value[s].push_back(w);
    }
    topsort();
    calEarlylater();
    return 0;
}

E. 旅游规划

题目描述

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

输入

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

输出

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

样例查看模式?

正常显示查看格式

输入样例1?

4?5?0?3\n
0?1?1?20\n
1?3?2?30\n
0?3?4?10\n
0?2?2?20\n
2?3?1?20

输出样例1

3?40

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=550;
pair<int,int> a[N][N];
int n,m,s,d;
void floyd()
{
     for(int k=0;k<n;k++)
     {
        for(int i=0;i<n;i++)
        {
            for(int j=0;j<n;j++)
            {
                if(a[i][j].first>a[i][k].first+a[k][j].first)
                {
                    a[i][j].first=a[i][k].first+a[k][j].first;
                    a[i][j].second=a[i][k].second+a[k][j].second;
                }
                else if(a[i][j].first==a[i][k].first+a[k][j].first)
                {
                    if(a[i][j].second>a[i][k].second+a[k][j].second)
                    {
                        a[i][j].second=a[i][k].second+a[k][j].second;
                        a[i][j].first=a[i][k].first+a[k][j].first;
                    }
                }
            }
        }
     }
}
int main()
{
    cin>>n>>m>>s>>d;
    //找s到d的最短路径
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<m;j++)
        {
            a[i][j].first=a[j][i].first
            =a[i][j].second=a[j][i].second
            =0x3f3f3f3f;//非常重要！！
        }
    }
    for(int i=0;i<m;i++)
    {
        int u,v,w,p;
        cin>>u>>v>>w>>p;
        a[u][v].first=a[v][u].first=w;
        a[v][u].second=a[u][v].second=p;
    }
    floyd();
    cout<<a[s][d].first<<" "<<a[s][d].second<<endl;
    return 0;
}

F. 拯救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"。

样例查看模式?

正常显示查看格式

输入样例1?

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

输出样例1

Yes

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int g[N][N];
int pd[N];
int x[N],y[N];
int k,n;
bool check(int n,int m,int x1,int y1,int x2,int y2)
{
    if((sqrt(x1*x1+y1*y1)-15<=k))g[0][n]=1;//ok
    if((sqrt(x2*x2+y2*y2)-15<=k))g[0][m]=1;//ok
    if((50-abs(x1)<=k)||(50-abs(y1)<=k))pd[n]=1;
    if((50-abs(x2)<=k)||(50-abs(y2)<=k))pd[m]=1;
    return (x1-x2)*(x1-x2)+(y1-y2)*(y1-y2)<=k*k;
}
bool flag=0;
void dfs(int n,int x)
{
    if(pd[x]==1)flag=1;
    for(int i=1;i<=n;i++)
    {
        if(g[x][i]==1)
        {
            g[x][i]=0;//跳完不再跳
            dfs(n,i);
        }
    }
}
int main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
    {
        cin>>x[i]>>y[i];
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            //可以跳的地方先统计
            g[i][j]=g[j][i]=check(i,j,x[i]
            ,y[i],x[j],y[j]);
        }
    }
    dfs(n,0);
    if(flag||(double)k>=(1.0*50*sqrt(2)-7.5))
    cout<<"Yes"<<endl;
    else
    {
        cout<<"No"<<endl;
    }
    return 0;
}