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

    (7条消息) 食用前须知（阅读并同意后在食用其他部分）_lxrrrrrrrr的博客-CSDN博客

    看完进来哈

    目录

    问题 A: 邻接矩阵存储的图，节点的出度和入度计算(附加代码模式)

    问题 B: 算法7-12：有向无环图的拓扑排序

    问题 C: 有向图是否存在环？

    问题 D: 是否为有效的拓扑序列

    问题 E: 案例6-2.6：最短工期

    ---------------------------------------概念-----------------------------------------

    最早发生时间：

    最迟发生时间：

    关键路径：

    --------------------------------------------------------------------------------------

    问题 F: 图-节点的最早发生时间

    问题 G: 图-节点的最迟发生时间

    问题 H: 图-边的最早发生时间

    问题 I: 图-边的最迟发生时间

    问题 J: 图-图的关键路径

    问题 A: 邻接矩阵存储的图，节点的出度和入度计算(附加代码模式)

    模拟即可

    1. #include 
    2. using namespace std;
    3. #define MAX_SIZE 200
    4. struct Graph{
    5.     int nodeNumber;
    6.     int adjMatrix[MAX_SIZE][MAX_SIZE];
    7. };
    8. void CalculateDegree(const Graph& g,int inDegree[],int outDegree[]){
    9.     int n=g.nodeNumber;
    10.     for(int i=0;i
    11.         for( int j=0;j
    12.             if(g.adjMatrix[i][j]==0){
    13.                 continue;
    14.             }
    15.             inDegree[j]+=1;
    16.             outDegree[i]+=1;
    17.         }
    18.     }
    19. }

    问题 B: 算法7-12：有向无环图的拓扑排序

    拓扑排序板子

    从每个入度为0的点开始宽搜即可

    1. #include 
    2. #define int long long
    3. #define pb push_back
    4. #define fer(i,a,b) for(int i=a;i<=b;++i)
    5. #define der(i,a,b) for(int i=a;i>=b;--i)
    6. #define all(x) (x).begin(),(x).end()
    7. #define pll pair
    8. #define et  cout<<'\n'
    9. #define xx first
    10. #define yy second
    11. using namespace std;
    12. const int N=1e6+10;
    13. int G[1000][1000];
    14. int n;
    15. int du[1000];
    16. vector<int> ans;
    17. bool tpst() {
    18.     int num=0;
    19.     stack<int> q;
    20.     fer(i,0,n-1){
    21.         if(du[i]==0){
    22.             q.push(i);
    23.         }
    24.     }
    25.     while(q.size()) {
    26.         int u=q.top();
    27.         q.pop();
    28.         ans.pb(u);
    29.         num++;
    30.         fer(v,0,n-1){
    31.             if(G[u][v]) {
    32.                 du[v]--;
    33.                 if(du[v]==0)
    34.                     q.push(v);  
    35.             } 
    36.         }
    37.     }
    38.     if(num==n){
    39.         return true;
    40.     }
    41.     else{
    42.         return false;
    43.     }
    44. }
    45. signed main()
    46. {
    47.     cin>>n;
    48.     fer(i,0,n-1){
    49.         fer(j,0,n-1){
    50.             cin>>G[i][j];
    51.             if(G[i][j]){
    52.                 du[j]++;
    53.             }
    54.         }
    55.     }
    56.     if(tpst()) {
    57.         for(auto t:ans){
    58.             cout<" ";
    59.         }
    60.         cout<<'\n';
    61.     }
    62.     else{
    63.         cout <<"ERROR\n";
    64.     } 
    65. }

    问题 C: 有向图是否存在环？

    判环的话

    并查集好写一点

    1. #include 
    2. #define int long long
    3. #define pb push_back
    4. #define fer(i,a,b) for(int i=a;i<=b;++i)
    5. #define der(i,a,b) for(int i=a;i>=b;--i)
    6. #define all(x) (x).begin(),(x).end()
    7. #define pll pair
    8. #define et  cout<<'\n'
    9. #define xx first
    10. #define yy second
    11. using namespace std;
    12. const int N=1e6+10;
    13. int p[N];
    14. int find(int x){
    15.     if(p[x]!=x)  p[x]=find(p[x]);
    16.     return p[x];
    17. }
    18.  
    19. signed main(){
    20.     int n,m;
    21.     while(cin>>n>>m){
    22.         if(!n && !m) break;
    23.         fer(i,1,n) p[i]=i;
    24.         bool fl=false;
    25.         fer(i,1,m){
    26.             int a,b;
    27.             cin>>a>>b;
    28.             if(find(a)!=find(b)){
    29.                 p[find(a)]=find(b);
    30.             }
    31.             else{
    32.                 fl=1;
    33.                 break;
    34.             }
    35.         }
    36.         if(fl){
    37.             cout<<"YES\n";
    38.         }
    39.         else{
    40.             cout<<"NO\n";
    41.         }
    42.     }
    43. }

    问题 D: 是否为有效的拓扑序列

    计算一下度数即可

    1. #include 
    2. #define int long long
    3. #define pb push_back
    4. #define fer(i,a,b) for(int i=a;i<=b;++i)
    5. #define der(i,a,b) for(int i=a;i>=b;--i)
    6. #define all(x) (x).begin(),(x).end()
    7. #define pll pair
    8. #define et  cout<<'\n'
    9. #define xx first
    10. #define yy second
    11. using namespace std;
    12. const int N=1e6+10;
    13. vector<int> v[N];
    14. int inv[N];
    15. int now[N];
    16. int n,m;
    17. int inx[N];
    18. bool check(){
    19.     fer(i,0,n) now[i]=inv[i];
    20.     for(int i=0;i
    21.         cin>>inx[i];
    22.     }
    23.     for(int i=0;i
    24.         if(now[inx[i]]!=0){
    25.             return false;
    26.         }
    27.         for(int j=0;jsize();j++){
    28.             now[v[inx[i]][j]]--;
    29.         }
    30.     }
    31.     return true;
    32. }
    33. signed main(){
    34.     cin>>n>>m;
    35.     fer(i,1,m){
    36.         int a,b;
    37.         cin>>a>>b;
    38.         v[a].pb(b);
    39.         inv[b]++;
    40.     }
    41.     int k;
    42.     cin>>k;
    43.     fer(i,1,k){
    44.         if(check()){
    45.             cout<<"YES"<
    46.         }
    47.         else cout<<"NO"<
    48.     }
    49.       
    50. }

    问题 E: 案例6-2.6：最短工期

    拓扑排序不那么板子的板子题

    1. #include 
    2. #define int long long
    3. #define pb push_back
    4. #define fer(i,a,b) for(int i=a;i<=b;++i)
    5. #define der(i,a,b) for(int i=a;i>=b;--i)
    6. #define all(x) (x).begin(),(x).end()
    7. #define pll pair
    8. #define et  cout<<'\n'
    9. #define xx first
    10. #define yy second
    11. using namespace std;
    12. const int N=1e6+10;
    13. int tmp[N];
    14. int h[N],e[N],ne[N],w[N],idx;
    15. int d[N],ans[N];
    16. queue<int> q;
    17. void add(int a,int b,int f){
    18.     e[idx]=b,w[idx]=f,ne[idx]=h[a],h[a]=idx++;
    19. }
    20. int n,m;
    21. void solve(){
    22.     int ans=0;
    23.     while(!q.empty()){
    24.         int t=q.front();
    25.         q.pop();
    26.         for(int i=h[t];i!=-1;i=ne[i]){
    27.             d[e[i]]--;
    28.             if(d[e[i]]==0) q.push(e[i]);
    29.             tmp[e[i]]=max(tmp[e[i]],w[i]+tmp[t]);
    30.             ans=max(ans,tmp[e[i]]);
    31.         }
    32.     }
    33.     fer(i,0,n-1){
    34.         if(d[i]!=0){
    35.             cout<<"Impossible\n";
    36.             return;
    37.         }
    38.     }
    39.     cout<'\n';
    40. }
    41. signed main(){
    42.     memset(h,-1,sizeof h);
    43.     cin>>n>>m;
    44.     fer(i,1,m){
    45.         int a,b,c;
    46.         cin>>a>>b>>c;
    47.         add(a,b,c);
    48.         d[b]++;
    49.     }
    50.     fer(i,0,n-1){
    51.         if(d[i]==0){
    52.             q.push(i);
    53.             tmp[i]=0;
    54.         }
    55.     }
    56.     solve();
    57. }

    ---------------------------------------概念-----------------------------------------

    作业上的概念模糊不清，这里稍作解释，是离散数学中的概念

    我们以这张图为例

    最早发生时间：

    从前往后，前驱结点到当前结点所需时间，取最大值。

    如上图中的节点4有两个前驱结点（节点2和3），节点2到节点4的最早发生时间是a1+a3也就是8，节点3到节点4的最早发生时间是a2+a4也就是12，因为12>8，所以节点4的最早发生时间是12.

    最迟发生时间：

    从后往前，后继结点的最迟发生时间-边权值，取最小值。

    也就是求一次最早发生时间，再从出度为0的点反向更新回来求出每个点的最迟时间

    关键路径：

    最早发生时间和最迟发生时间相同的结点即为关键路径上的节点。

     也就是两个都要求一遍呗

    而边的最早最迟发生时间大家看作业上的图就知道了，就是看对应的点的最早最迟发生时间

    所以我们可以先求点的然后在遍历一遍求出边的最早最迟发生时间

    --------------------------------------------------------------------------------------

    下列代码我没有用拓扑排序写

    而是直接宽搜的，然后松弛

    拓扑排序本质就是bfs呗

    因为后续涉及到对边的操作，所以我用了链式前向星存图

    不懂可以csdn一下，很简单的

    问题 F: 图-节点的最早发生时间

    边bfs边更新每个点的答案

    1. #include 
    2. #define int long long
    3. #define pb push_back
    4. #define fer(i,a,b) for(int i=a;i<=b;++i)
    5. #define der(i,a,b) for(int i=a;i>=b;--i)
    6. #define all(x) (x).begin(),(x).end()
    7. #define pll pair
    8. #define et  cout<<'\n'
    9. #define xx first
    10. #define yy second
    11. using namespace std;
    12. const int N=1e6+10;
    13. int h[N],w[N],e[N],ne[N],idx;
    14. void add(int a, int b, int c)
    15. {
    16.     e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++ ;
    17. }
    18. int dist[N];
    19. int n,m;
    20. void bfs(){
    21.     memset(dist,0,sizeof dist);
    22.     dist[1]=0;
    23.     queue<int> q;
    24.     q.push(1);
    25.     while(q.size()){
    26.         auto tp=q.front();
    27.         q.pop();
    28.         for(int i=h[tp];i!=-1;i=ne[i]){
    29.             int j=e[i];
    30.             if(w[i]+dist[tp]>dist[j]){
    31.                 dist[j]=dist[tp]+w[i];
    32.                 q.push(j);
    33.             }
    34.         }
    35.     }
    36. }
    37. signed main(){
    38.     memset(h,-1,sizeof h);
    39.     cin>>n>>m;
    40.     fer(i,1,m){
    41.         int a,b,w;
    42.         cin>>a>>b>>w;
    43.         add(a+1,b+1,w);
    44.     }
    45.     bfs();
    46.     fer(i,1,n){
    47.         cout<'\n';
    48.     }
    49. }

    问题 G: 图-节点的最迟发生时间

    我们需要建两张图，一张正向图一张反向图

    从第一张图bfs出去求出最早时间，然后在第二张图反向bfs一遍

    1. #include 
    2. #define int long long
    3. #define pb push_back
    4. #define fer(i,a,b) for(int i=a;i<=b;++i)
    5. #define der(i,a,b) for(int i=a;i>=b;--i)
    6. #define all(x) (x).begin(),(x).end()
    7. #define pll pair
    8. #define et  cout<<'\n'
    9. #define xx first
    10. #define yy second
    11. using namespace std;
    12. const int N=1e6+10;
    13. int h[N],w[N],e[N],ne[N],idx;
    14. int h2[N],w2[N],e2[N],ne2[N],idx2;
    15. void add1(int a, int b, int c)
    16. {
    17.     e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++ ;
    18. }
    19. void add2(int a, int b, int c)
    20. {
    21.     e2[idx2]=b,w2[idx2]=c,ne2[idx2]=h2[a],h2[a]=idx2++ ;
    22. }
    23. int dist[N];
    24. int dist2[N];
    25. int n,m;
    26. void bfs(){
    27.     memset(dist,0,sizeof dist);
    28.     dist[1]=0;
    29.     queue<int> q;
    30.     q.push(1);
    31.     while(q.size()){
    32.         auto tp=q.front();
    33.         q.pop();
    34.         for(int i=h[tp];i!=-1;i=ne[i]){
    35.             int j=e[i];
    36.             if(w[i]+dist[tp]>dist[j]){
    37.                 dist[j]=dist[tp]+w[i];
    38.                 q.push(j);
    39.             }
    40.         }
    41.     }
    42.     memset(dist2,0x3f,sizeof dist2);
    43.     queue<int> q2;
    44.     fer(i,1,n){
    45.         if(h[i]==-1){
    46.             dist2[i]=dist[i];
    47.             q2.push(i);
    48.         }
    49.     }
    50.  
    51.     while(q2.size()){
    52.         auto tp=q2.front();
    53.         q2.pop();
    54.         for(int i=h2[tp];i!=-1;i=ne2[i]){
    55.             int j=e2[i];
    56.             if(dist2[tp]-w2[i]
    57.                 dist2[j]=dist2[tp]-w2[i];
    58.                 q2.push(j);
    59.             }
    60.         }
    61.     }
    62. }
    63. int res[N];
    64. signed main(){
    65.     memset(h,-1,sizeof h);
    66.     memset(h2,-1,sizeof h2);
    67.     cin>>n>>m;
    68.     fer(i,1,m){
    69.         int a,b,w;
    70.         cin>>a>>b>>w;
    71.         add1(a+1,b+1,w);
    72.         add2(b+1,a+1,w);
    73.     }
    74.     bfs();
    75.     fer(i,1,n){
    76.         cout<"\n";
    77.     }
    78. }

    问题 H: 图-边的最早发生时间

    和点的最早发生时间一样

    这条边是那个点引出来的答案就和这个点的最早发生时间一样

    1. #include 
    2. #define int long long
    3. #define pb push_back
    4. #define fer(i,a,b) for(int i=a;i<=b;++i)
    5. #define der(i,a,b) for(int i=a;i>=b;--i)
    6. #define all(x) (x).begin(),(x).end()
    7. #define pll pair
    8. #define et  cout<<'\n'
    9. #define xx first
    10. #define yy second
    11. using namespace std;
    12. const int N=1e6+10;
    13. int h[N],w[N],e[N],ne[N],idx;
    14. int res[N];
    15. void add(int a, int b, int c)
    16. {
    17.     e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++ ;
    18. }
    19. int dist[N];
    20. int n,m;
    21. void bfs(){
    22.     memset(dist,0,sizeof dist);
    23.     dist[1]=0;
    24.     queue<int> q;
    25.     q.push(1);
    26.     while(q.size()){
    27.         auto tp=q.front();
    28.         q.pop();
    29.         for(int i=h[tp];i!=-1;i=ne[i]){
    30.             int j=e[i];
    31.             if(w[i]+dist[tp]>dist[j]){
    32.                 dist[j]=dist[tp]+w[i];
    33.                 q.push(j);
    34.             }
    35.         }
    36.     }
    37. }
    38. signed main(){
    39.     memset(h,-1,sizeof h);
    40.     cin>>n>>m;
    41.     fer(i,1,m){
    42.         int a,b,w;
    43.         cin>>a>>b>>w;
    44.         add(a+1,b+1,w);
    45.     }
    46.     bfs();
    47.     fer(node,1,n){
    48.         for(int i=h[node];i!=-1;i=ne[i]){
    49.             res[i]=dist[node];
    50.         }
    51.     }
    52.     fer(i,0,m-1){
    53.         cout<'\n';
    54.     }
    55. }

    问题 I: 图-边的最迟发生时间

    和点的最迟发生时间一样

    这条边指向那个点的答案就是这个点的最迟发生时间减去权值

    1. #include 
    2. #define int long long
    3. #define pb push_back
    4. #define fer(i,a,b) for(int i=a;i<=b;++i)
    5. #define der(i,a,b) for(int i=a;i>=b;--i)
    6. #define all(x) (x).begin(),(x).end()
    7. #define pll pair
    8. #define et  cout<<'\n'
    9. #define xx first
    10. #define yy second
    11. using namespace std;
    12. const int N=1e6+10;
    13. int h[N],w[N],e[N],ne[N],idx;
    14. int h2[N],w2[N],e2[N],ne2[N],idx2;
    15. void add1(int a, int b, int c)
    16. {
    17.     e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++ ;
    18. }
    19. void add2(int a, int b, int c)
    20. {
    21.     e2[idx2]=b,w2[idx2]=c,ne2[idx2]=h2[a],h2[a]=idx2++ ;
    22. }
    23. int dist[N];
    24. int dist2[N];
    25. int n,m;
    26. void bfs(){
    27.     memset(dist,0,sizeof dist);
    28.     dist[1]=0;
    29.     queue<int> q;
    30.     q.push(1);
    31.     while(q.size()){
    32.         auto tp=q.front();
    33.         q.pop();
    34.         for(int i=h[tp];i!=-1;i=ne[i]){
    35.             int j=e[i];
    36.             if(w[i]+dist[tp]>dist[j]){
    37.                 dist[j]=dist[tp]+w[i];
    38.                 q.push(j);
    39.             }
    40.         }
    41.     }
    42.     memset(dist2,0x3f,sizeof dist2);
    43.     queue<int> q2;
    44.     fer(i,1,n){
    45.         if(h[i]==-1){
    46.             dist2[i]=dist[i];
    47.             q2.push(i);
    48.         }
    49.     }
    50.  
    51.     while(q2.size()){
    52.         auto tp=q2.front();
    53.         q2.pop();
    54.         for(int i=h2[tp];i!=-1;i=ne2[i]){
    55.             int j=e2[i];
    56.             if(dist2[tp]-w2[i]
    57.                 dist2[j]=dist2[tp]-w2[i];
    58.                 q2.push(j);
    59.             }
    60.         }
    61.     }
    62. }
    63. int res[N];
    64. signed main(){
    65.     memset(h,-1,sizeof h);
    66.     memset(h2,-1,sizeof h2);
    67.     cin>>n>>m;
    68.     fer(i,1,m){
    69.         int a,b,w;
    70.         cin>>a>>b>>w;
    71.         add1(a+1,b+1,w);
    72.         add2(b+1,a+1,w);
    73.     }
    74.     bfs();
    75.     fer(node,1,n){
    76.         for(int i=h[node];i!=-1;i=ne[i]){
    77.             int j=e[i];
    78.             res[i]=dist2[j]-w[i];
    79.         }
    80.     }
    81.     fer(i,0,m-1){
    82.         cout<'\n';
    83.     }
    84. }

    问题 J: 图-图的关键路径

    两个都求一边

    然后看相等

    1. #include 
    2. #define int long long
    3. #define pb push_back
    4. #define fer(i,a,b) for(int i=a;i<=b;++i)
    5. #define der(i,a,b) for(int i=a;i>=b;--i)
    6. #define all(x) (x).begin(),(x).end()
    7. #define pll pair
    8. #define et  cout<<'\n'
    9. #define xx first
    10. #define yy second
    11. using namespace std;
    12. const int N=1e6+10;
    13. int h[N],w[N],e[N],ne[N],idx;
    14. int h2[N],w2[N],e2[N],ne2[N],idx2;
    15. void add1(int a, int b, int c)
    16. {
    17.     e[idx]=b,w[idx]=c,ne[idx]=h[a],h[a]=idx++ ;
    18. }
    19. void add2(int a, int b, int c)
    20. {
    21.     e2[idx2]=b,w2[idx2]=c,ne2[idx2]=h2[a],h2[a]=idx2++ ;
    22. }
    23. int dist[N];
    24. int dist2[N];
    25. int n,m;
    26. void bfs(){
    27.     memset(dist,0,sizeof dist);
    28.     dist[1]=0;
    29.     queue<int> q;
    30.     q.push(1);
    31.     while(q.size()){
    32.         auto tp=q.front();
    33.         q.pop();
    34.         for(int i=h[tp];i!=-1;i=ne[i]){
    35.             int j=e[i];
    36.             if(w[i]+dist[tp]>dist[j]){
    37.                 dist[j]=dist[tp]+w[i];
    38.                 q.push(j);
    39.             }
    40.         }
    41.     }
    42.     memset(dist2,0x3f,sizeof dist2);
    43.     queue<int> q2;
    44.     fer(i,1,n){
    45.         if(h[i]==-1){
    46.             dist2[i]=dist[i];
    47.             q2.push(i);
    48.         }
    49.     }
    50.   
    51.     while(q2.size()){
    52.         auto tp=q2.front();
    53.         q2.pop();
    54.         for(int i=h2[tp];i!=-1;i=ne2[i]){
    55.             int j=e2[i];
    56.             if(dist2[tp]-w2[i]
    57.                 dist2[j]=dist2[tp]-w2[i];
    58.                 q2.push(j);
    59.             }
    60.         }
    61.     }
    62. }
    63. int res[N];
    64. int res2[N];
    65. vector edge;
    66. signed main(){
    67.     memset(h,-1,sizeof h);
    68.     memset(h2,-1,sizeof h2);
    69.     cin>>n>>m;
    70.     fer(i,1,m){
    71.         int a,b,w;
    72.         cin>>a>>b>>w;
    73.         edge.push_back({a,b});
    74.         add1(a+1,b+1,w);
    75.         add2(b+1,a+1,w);
    76.     }
    77.     bfs();
    78.     fer(node,1,n){
    79.         for(int i=h[node];i!=-1;i=ne[i]){
    80.             res[i]=dist[node];
    81.         }
    82.     }
    83.     fer(node,1,n){
    84.         for(int i=h[node];i!=-1;i=ne[i]){
    85.             int j=e[i];
    86.             res2[i]=dist2[j]-w[i];
    87.         }
    88.     }
    89.     fer(i,0,m-1){
    90.         if(res[i]==res2[i]){
    91.             cout<"-->"<":"<'\n';
    92.         }
    93.     }
    94. }

  • 相关阅读:
    大数据培训课程之序列化案例实操
    人工智能轨道交通行业周刊-第14期（2022.9.12-9.18）
    wsl-Ubuntu18.04子系统使用cuda
    SpringBoot篇---第四篇
    js脚本化css
    六、鼎捷T100生产管理之生产入库管理篇
    Git代码回归到指定commit
    解决mybatis用Map返回的字段全变大写的问题
    分布式环境下的接口幂等性
    【开发篇】三、web下单元测试与mock数据
  • 原文地址：https://blog.csdn.net/m0_61735576/article/details/127927479