Preface

学校码图的数据结构实验第四题;

马上要完成期末作业辣；

让我们开始吧！

Content

这里是题目:矩阵连乘算法

分别用邻接矩阵和邻接链表两种数据结构实现图的深度优先遍历算法，输出遍历的结点序列，并分析算法的时间复杂度。

提交格式：邻接矩阵数据结构实现void solveA(int n, int m, int e[][2], int out[])函数。邻接链表数据结构实现void solveB(int n, int m, int e[][2], int out[])函数。参数n为结点个数，m为边条数，e为所有边，out为输出序列。1<=n<=3000,1<=m<=100000,0<=e[i][j]<n。遍历的起始结点为0，邻接矩阵数据结构中按行从左到右遍历邻居结点，邻接链表数据结构中按存储顺序遍历邻居结点，图为无向图。请不要printf输出任何内容。

输入样例： n=5,m=10,e={{2,4},{3,0},{0,2},{3,1},{4,1},{0,1},{3,4},{2,3},{1,2},{0,4}} 输出样例： solveA：out={0,1,2,3,4} solveB：out={0,3,1,4,2}

观察数据好像有点小()，可能像搜索、动态规划之类的算法；

再看一眼，矩阵乘法中的数乘原来是这个意思：

对于一个的矩阵和的矩阵,得到的的矩阵进行的数乘次数为；

那么通过适当的加括号，可以调整矩每次相乘矩阵的规模，从而尽可能减小数乘的次数；

对于样例的答案是这样算出来的：

;

如果连这个也看懂的话，相信转移方程也不会很难的；

对于要解决问题的数组p[],我们维护两端得到答案m[i][j]，要解决的问题是m[1][n],顺便维护一下加括号的方式s[i][j];

转移方程如下：

都看到这里了，快去试试吧！

#include <iostream>
#include <vector>
#include <string.h>
const int MOD=1e9+7;
const int maxn=505;
typedef long long ll;
int m[maxn][maxn];
int s[maxn][maxn];
void dp(int n,int p[]){ 
    for(int i=1;i<=n;i++) m[i][i]=0;
    for(int d=2;d<=n;d++){
        for(int i=1;i<=n+1-d;i++){
            int j=i+d-1;
            m[i][j]=INT_MAX;
            for(int k=i;k<=j-1;k++) {
                int tmp = (m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j])%MOD;
                if(m[i][j]>tmp) {
                    m[i][j]=tmp;
                    s[i][j]=k;
                }
            }    
        }
    }
}
// 格式化输出函数，构建输出序列
void pr(int i, int j, int n , std::vector<int> &out) {
    if (i == j) {
        out.push_back(i);
        return;
    }
    out.push_back(-1); // '(' 替换为 -1
    pr(i, s[i][j], n,  out);
    pr(s[i][j] + 1, j, n, out);
    out.push_back(-2); // ')' 替换为 -2
}

void solve(int n, int p[], int out[]) { 
    dp(n,p);
    std::vector<int> OUT;
    pr(1, n, n, OUT);

    out[0] = m[1][n] % MOD;  
    for (int i = 1; i <= OUT.size(); ++i) {
        out[i] =OUT [i - 1];
    }
}

Remark

保送码图分数，期末+10！

数据结构与算法实验:矩阵连乘算法

Preface

Content

Remark