638题一题三解

解法一记忆化dfs

不难看出，每一个needs就是一个状态。根据题干，本质上是一个有向无环图，按照记忆化写就行
解法二 BFS广搜
暴搜思路正确，也不会超时，但是性能比dfs差，毕竟是广搜，搜到终点(也就是needs=000)时，还不能立即结束，因为还可能存在其他使得终点的价格更小的方案，所以还得遍历完所有的情况之后，逐一比较结果再返回。
解法三 Dijtsra算法 2022.1.14更
Dijtsra其实本质上也是BFS+贪心，所以应用在本题的有向无环图，思路也是正确的，幸能比bfs好，比dfs差。
优先队列存储每一个状态，设置两个变量，一个HashSet<List<Integer>>相当于visited[]，用来标记已经记录过最段路径的状态,一个HashMap<List<Integer>,Integer>相当于distance[]，用来记录当前状态的最短路径(还不一定是最短).

图总结

只要是有向无环图，并且要求出最优解，就可以通过BFS来求解，因为迪杰特斯拉算法本质上就是贪心+bfs，所以可以用bfs来求解的题一定可以用迪杰特斯拉算法。

堆优化的迪杰特斯拉算法中状态的表示方法有两种，一种是用一维数组distance[]来表示，另一种是用哈希表存链表+距离表示，如果链表的表示过于复杂，可以用String存状态，可能会比较麻烦，应为可能涉及到下标的取值。

图论算法存图的三种方法

Uva1601 将点存为图

// 记录点的个数 和 存边的链式存图的idx类似
int cnt;
// 存第cnt个点的下标x,y
int[] x;int[] y;    // x[cnt] y[cnt]
// 
int[][] id;  //id[x][y]=cnt 存某个下标对应的是第几个点
// 将点与点建立联系
int[] deg=new int[cnt];  //存第cnt个点周围有几个点  cnt<=5 还有点本身 可以不移动
int[][] G=new int[cnt][5]   // G[cnt][idx]=cnt; 存某个点的idx方向上对应点的
for(char c:maze){
    for(int d:direction){
        if(d也是点) G[cnt][idx]=d; 
    }
}

类edge

class Edge{
    // v:起点 g:终点 w:权值
    int v,g,w
    edge(){}
}

邻接表，链式星向存图

int N,M; //N:点的个数 M:边个数
int[] he=new int[N];
int[] w=new int[M];
int[] ne=new int[M];
int[] e=new int[M];
// 记录边的个数
idx=0;
// 初始化所有的节点都没有边
Arrays.fill(he,-1)
void add(int u,int v,int w){
    e[v]=w;
    ne[v]=he[u];
    he[u]=idx
    w[idx]=w;
}
void iteration(){
    for(int i=he[w];i!=-1;i=he[i]){
        // 取边对应的终点
        int j=e[i];
    }
}

邻接矩阵

图论算法模板

floyd应用在图中存在边权为负值的情况的算法，dij是用在边权非负的情况下的算法。

Floyd算法

public static void main(int[][] graph,int n,int k){
    // 设置path 记录两个节点中间节点 如果为-1 表示直达
    int[][] path=new int[][];
    // v为中间节点 i为起始节点 j为终点
    for(int v=1;v<=n;v++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(distance[i][v]+distance[v][j]<distance[i][j]){
                    path[i][j]=v;
                    distance[i][j]=distance[i][v]+distance[v][j];
                }
            }
        }
    }
}

bellman朴素算法伪代码

List<Edge> list;
        for(int i=1;i<=n-1;i++){
            for (Edge edge : list) {
                int u = edge.u;
                int v = edge.v;
                int w = edge.w;
                if(distance[u]+w<distance[v]){
                    distance[v]=distance[u]+w;
                }
            }
        }
        // 检查有无负权环
        // 有两种写法 一种再跑一遍bell，一种遍历一次边即可
        //1.
        for(Edge edge:list){}
        //2.
        for(){
            for(Edge edge:list){}
        }

bellman算法队列优化伪代码

注意1：一个节点可能入队列多次，所以每次queue.poll之后都必须visited[node]=0;
注意2：如果进入队列超过n次，false. 换句话说，如果一个节点入队列的次数小于等于n，都可以接受。不采用队列优化的测试次数。但是，我觉得这里应该是cnt[node]>=n,因为在朴素bellman中，最多遍历n-1次，n不接受.

注意3：一定要在更新了距离之后再将visited[j]=1.一个反例[1,2,1],[2,3,7],[1,3,4],[2,1,2].

// 链式星向存图 e he w ne
public static void main(int[][] graph){
    int[] distance;
    // 标记是否在队列
    int[] visited;
    // 记录一共入队列几次
    int[] cnt;
    // 起点的距离为0
    Queue<Integer> queue=new ArrayQueue<>();
    queue.offer(k);
    // 初始化起点
    visited[k]=1;
    distance[k]=0;
    // 一个起点可以入队列多次
    while(!queue.isnull()){
        node=queue.poll();
        visited[node]=0;
        for(int i=he[node];i!=-1;i=ne[i]){
            int j=e[i];
            if(distance[j]>distance[node]+w[i]){
                distance[j]=distance[node]+w[i];
                // 注意 这一行一定要放在更新距离之后
                if(visited[j]==1) continue;
                queue.offer(j);
                visited[j]=1;
                cnt[j]++;
                if(cnt[j]>n) return false;
            }
        }
    }
    return true;
}

Dijtsra堆优化伪代码

public static void main(){
    // 设置两个变量
    int[] visited;
    int[] distance;
    PriorityQueue<int[]> queue;
    while(){
        poll();
        // 防止遍历过的点再次被遍历
        if(visited) continue;
        visited=1;
        // 遍历点
        for(){}
    }
}

Dijtsra伪代码

public static void main(){
    // 设置两个变量
    int[] visited;
    int[] distance;
    // 外层 遍历轮数
    for(){
        // 用于记录当前已经有距离的最小距离以及对应的节点
        int minIdx=-1;
        int minDis=Integer.MAX;
        for(){
            if(<){
                minIdx=;
                minDis=;
            }
        };
        if(minIdx==-1) return -1;
        // 用于更新与minIdx相连接的点的距离
        for(){
            int s=minDis+graph[i][j]
            if(s<distance[j]) distance[j]=s;
        }
    }
}

`2022.2.17`最小生成树

Prime算法

适用于求边稠密的图，因为算法的时间复杂度与边的数量无关，而与顶点有关.O(n^2)，其中n为顶点的数量。
从规定的顶点出发，按照dijtsra算法跑一遍，就可以找到具有最小边权值和的最小生成树。
但是还是和dij算法存在细微差别，首先dij算法求的是某个顶点到其余各个顶点最短距离。其次，对于对于辅助数组的设置也不同，dij算法中利用distance[i]数组存储出发点到下标顶点的当前最短路径。而在prime算法中利用closedge[i]数组存储某个顶点具有的最小权值边，以及该最小权值边的另一端顶点。
Kruscal算法
利用MFset(并查集)和对边权值进行排序求最小生成树的算法。适用于求边稀疏图。O(nlogn)，其中n为边的数量

2022.2.21 找关节点+关键路径

关节点

如果根节点存在多颗子树，则该根节点是一个关节点
如果某个节点的子节点没有和祖先节点相连，则该节点是一个关节点
关键路径

递推

首先通过拓扑排序正序递推求每个结点的ee(最早开始时间)
然后将每个结点的el全部赋值给ee.通过逆序拓扑求每个节点的el(el=Math.min(el,el[i+1]-dut(i,i+1)))
上一步的逆序拓扑既可以通过正序拓扑设置一个辅助栈T来实现。也可以通过dfs来实现.