北京化工大学数据结构2022/11/24作业 题解

后天要去最后一场区域赛了，文字先鸽

打完润了 

目录

问题 A: 图的最小生成树-Prim算法

问题 B: 图的最小生成树-Kruskal算法

问题 C: 算法7-9：最小生成树

问题 D: 算法7-15：迪杰斯特拉最短路径算法

问题 E: 算法7-16：弗洛伊德最短路径算法

问题 F: 图的最短路径-Floyd算法输出最短路径包含的边

---

问题 A: 图的最小生成树-Prim算法

#include 
#define int long long
#define pb push_back
#define fer(i,a,b) for(int i=a;i<=b;++i)
#define der(i,a,b) for(int i=a;i>=b;--i)
#define all(x) (x).begin(),(x).end()
#define pll pair
#define et  cout<<'\n'
#define xx first
#define yy second
using namespace std;
template <typename _Tp>void input(_Tp &x){
    char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
    x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
    if(f)x=-x;
}
template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
const int N = 110;
int arr[100][100];
int cost[N],adj[N];
signed main(){
    int n;
    cin>>n;
    fer(i,0,n-1){
        fer(j,0,n-1){
            cin>>arr[i][j];
        }
    }
    fer(i,0,n-1){
        if(arr[0][i]!=0){
            cout<" "<0][i]<<" "<<"0"<<'\n';
        }
        else{
            cout<" - -"<<'\n';
        }
    }
  
}

问题 B: 图的最小生成树-Kruskal算法

这题非要这咱手写排序

巨**

#include 
#define int long long
#define pb push_back
#define fer(i,a,b) for(int i=a;i<=b;++i)
#define der(i,a,b) for(int i=a;i>=b;--i)
#define all(x) (x).begin(),(x).end()
#define pll pair
#define et  cout<<'\n'
#define xx first
#define yy second
using namespace std;
template <typename _Tp>void input(_Tp &x){
    char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
    x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
    if(f)x=-x;
}
template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
const int N=1000,M=N*2;
struct edg
{
    int arc,ver,c;
}; 
signed main()
{
    int n;
    cin>>n;
    vector g;
    for(int i=0;i
    {
        for(int j=0;j
        {
            int x;
            cin>>x;
            if(x)
            {
 
                g.push_back({i,j,x});
            }
        }
    }
    for(int i=0;isize();i++)
    {
        for(int j=i+1;jsize();j++)
        {
            if(g[i].c>g[j].c)
            {
                swap(g[i],g[j]);
            }
        }
    }
    for(int i=0;isize();i++){
        cout<<"<"<","<">"<<":"<'\n';
    }
}

问题 C: 算法7-9：最小生成树

kruskal板子

#include 
#define int long long
#define pb push_back
#define fer(i,a,b) for(int i=a;i<=b;++i)
#define der(i,a,b) for(int i=a;i>=b;--i)
#define all(x) (x).begin(),(x).end()
#define pll pair
#define et  cout<<'\n'
#define xx first
#define yy second
using namespace std;
template <typename _Tp>void input(_Tp &x){
    char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
    x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
    if(f)x=-x;
}
template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
const int N=1000,M=N*2;
int p[N];
const int INF=1000000007;
struct Edge
{
    int a,b,w;
    bool operator< (const Edge &W)const
    {
        return w < W.w;
    }
}edges[M];
int find(int x)
{
    if (p[x] != x) p[x] = find(p[x]);
    return p[x];
}
int n,m;
int kruskal()
{
    sort(edges, edges + m);
    for (int i = 1; i <= n; i ++ ) p[i]=i;
    int res = 0, cnt = 0;
    for (int i = 0; i < m; i ++ )
    {
        int a = edges[i].a, b = edges[i].b, w = edges[i].w;
 
        a = find(a), b = find(b);
        if (a != b)
        {
            p[a] = b;
            res += w;
            cnt ++ ;
        }
    }
    if (cnt < n - 1) return INF;
    return res;
}
 
signed main(){
    cin>>n;
    fer(i,1,n){
        fer(j,1,n){
            int xx;
            cin>>xx;
            if(xx){
                edges[m]={i,j,xx};
                m++;
            }
        }
    }
    cout<<kruskal();
}

问题 D: 算法7-15：迪杰斯特拉最短路径算法

#include 
#define int long long
#define pb push_back
#define fer(i,a,b) for(int i=a;i<=b;++i)
#define der(i,a,b) for(int i=a;i>=b;--i)
#define all(x) (x).begin(),(x).end()
#define pll pair
#define et  cout<<'\n'
#define xx first
#define yy second
using namespace std;
template <typename _Tp>void input(_Tp &x){
    char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
    x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
    if(f)x=-x;
}
template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
const int N=1000,inf=0x3f3f3f3f; 
int w[N][N];
int dist[N];
int vis[N];
void dijistra(int n,int be){
    memset(dist,0x3f,sizeof dist);
    vis[be]=1;
    dist[be]=0;
    int now=be;
    for(int i=0;i-1;i++){
        for( int j=0;j
            if(w[now][j]==0||vis[j]==1) continue;
            dist[j]=min(dist[j],dist[now]+w[now][j]);
        }
        int ne=0,minn=inf;
        for( int j=0;j
            if(vis[j]==1) continue;
            if(dist[j]
                minn=dist[j];
                ne=j;
            }
        }
        now=ne;
        vis[ne]=1;
    }  
    return ; 
}
signed main(){
    int n;
    int be;
    input(n,be);
    fer(i,0,n-1){
        fer(j,0,n-1){
            input(w[i][j]);
        }
    }
    dijistra(n,be);
    for(int i=0;i
        if(i==be){
            continue;
        }
        else{
            cout<" ";
        }
    }
}

问题 E: 算法7-16：弗洛伊德最短路径算法

#include 
#define int long long
#define pb push_back
#define fer(i,a,b) for(int i=a;i<=b;++i)
#define der(i,a,b) for(int i=a;i>=b;--i)
#define all(x) (x).begin(),(x).end()
#define pll pair
#define et  cout<<'\n'
#define xx first
#define yy second
using namespace std;
template <typename _Tp>void input(_Tp &x){
    char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
    x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
    if(f)x=-x;
}
template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
int mat[500][500];
int dis[500][500];
signed main(){
    int n;
    cin>>n;
    memset(dis,0x3f,sizeof dis);
    for(int i=0;i
        for(int j=0;j
            input(mat[i][j]);
            if(mat[i][j]!=0)
                dis[i][j]=mat[i][j];
        }
    }
    for(int i=0;i
        dis[i][i]=0;
    for(int k=0;k
        for(int i=0;i
            for(int j=0;j
                if(dis[i][k]+dis[k][j]
                    dis[i][j]=dis[i][k]+dis[k][j];
            }
        }
    }
    for(int i=0;i
        for(int j=0;j
            cout<" ";
        }
        cout<<'\n';
    }
}

问题 F: 图的最短路径-Floyd算法输出最短路径包含的边

#include 
#define int long long
#define pb push_back
#define fer(i,a,b) for(int i=a;i<=b;++i)
#define der(i,a,b) for(int i=a;i>=b;--i)
#define all(x) (x).begin(),(x).end()
#define pll pair
#define et  cout<<'\n'
#define xx first
#define yy second
using namespace std;
template <typename _Tp>void input(_Tp &x){
    char ch(getchar());bool f(false);while(!isdigit(ch))f|=ch==45,ch=getchar();
    x=ch&15,ch=getchar();while(isdigit(ch))x=x*10+(ch&15),ch=getchar();
    if(f)x=-x;
}
template <typename _Tp,typename... Args>void input(_Tp &t,Args &...args){input(t);input(args...);}
int dij[101][101];
int path[101][101];
int a[101][101];           
signed main(){
    int n;
    input(n);
    fer(i,0,n-1)
        fer(j,0,n-1){
            int x,y;
            input(x,y);
            if(x!=-1){
                dij[i][j] = x;
                path[i][j] = y;
            }
        }
    int x,y;
    input(x,y);
    int p = path[x][y];
 
    stack<int>s;
    s.push(y);
    while (p!=x)
    {
        s.push(p);
        p = path[x][p];
    }
    s.push(x);
    cout<'\n';
    while(s.size()){
        auto t=s.top();
        cout<" ";
        s.pop();
    }
}