题解 | #扩散II#

一.题目描述
NC570扩散II
n个节点，n-1条边使之连通(两两之间是联通的)，每条边代表距离为1。一共m次污染，每次发生在数组元素x[i]，影响范围是与发生点距离不超过y[i]，影响范围所有节点污染指数增加z[i]，污染指数初始值全部为0，求m次污染发生后，每个节点的污染指数。

二.算法(搜索)
理解题目意思后我们可以利用搜索来解决，我们可以用邻接矩阵构建一个无向图，然后对每次发生污染的初始节点进行一次遍历，对其进行深度优先遍历，搜索的层次为y[i]，对每一个被搜索到的点进行节点污染指数增加z[i]，求出m次污染发生后每个节点的污染指数。
(图片来源牛客)
所以整体搜索的思路也变的很清晰了，我们对每一个点进行搜索，对其搜索的前驱进行记录，对其搜索的深度进行记录，前者是为了减少重复搜索，后者是为了使其距离不超过过y[i]。并且在搜索过程中不断对每个结点的污染指数进行更新，最后返回，下面是完整代码：

class Solution {
public:
    void dfs(vector<vector<int>>&mp,vector<int>& num, int pre, int x, int y, int z, int d) {
        //已有的污染指数进行更新
        num[x]+=z;
        for(int i=0;i <mp[x].size(); i++){
            //是否等于前驱节点 不等于才可以继续搜索
            if (mp[x][i]!=pre){
                //判断是否可以到达
                if (d+1<= y){
                    //可以到达就进行搜索
                    dfs(mp,num, x,mp[x][i],y,z,d+1);
                }
            }
        }
    }
    vector<int> solve(int n, int m, vector<int>& u, vector<int>& v, vector<int>& x, vector<int>& y, vector<int>& z) {
        vector<vector<int> > mp(n+1);
        vector<int> num(n+1, 0);
        //建图和存图
        for(int i = 0; i < u.size(); i++){ 
            mp[u[i]].push_back(v[i]);
            mp[v[i]].push_back(u[i]);
        }
        //对每一个点开始深搜 并对每一个工厂的污染指数进行记录
        for(int i =0;i<m; i++){
            dfs(mp,num,-1,x[i],y[i],z[i],0); 
        }
        //节点编号是从1开始的 删去下标为0的结点
        num.erase(num.begin());
        return num;
    }
};

时间复杂度：每个结点都需要去搜索其所有的污染次数，所以复杂度是
空间复杂度：需要空间来存储每个节点的最后的污染指数
优缺点：思路简单，代码实现也简单。
三.算法(java的实现)
我们也可以利用java用链式前向星来存图来解决问题，思路和前一种算法大体一样，下面是完整代码：

import java.util.*;


public class Solution {
    public static int[] e,nx,w,h,cn;
    public static int cnt;
    static{
        cnt=0;
        cn=new int[200005];
        e=new int[200005];
        nx=new int[200005];
        w=new int[200005];
        h=new int[200005];
        for(int i=0;i<200005;i++){
            h[i]=-1;
            cn[i]=0;
        }
    }
    public void add(int a,int b,int c){
        e[cnt]=b;
        w[cnt]=c;
        nx[cnt]=h[a];
        h[a]=cnt++;
    }
    public void dfs(int pre, int x, int y, int z, int d){
        cn[x]+=z;
        for(int i=h[x];i!=-1;i=nx[i]){
            int ed=e[i];
            //是否等于前驱节点 不等于才可以继续搜索
            if (ed!=pre){
                //判断是否可以到达
                if (d+1<= y){
                    //可以到达就进行搜索
                    dfs(x,ed,y,z,d+1);
                }
            }
        }
    }
    public int[] solve (int n, int m, int[] u, int[] v, int[] x, int[] y, int[] z) {
        int[] ans=new int[n];
        //利用链式前向星进行存图
        for(int i=0;i<u.length;i++){ 
            add(u[i],v[i],1);
            add(v[i],u[i],1);
        }
        for(int i =0;i<m; i++){
            dfs(-1,x[i],y[i],z[i],0); 
        }
        //确保返回值 符合要求
        for(int i=0;i<n;i++){
            ans[i]=cn[i+1];
        }
        return ans;
    }
}

时间复杂度：每个结点都需要去搜索其所有的污染次数，所以复杂度是
空间复杂度：需要空间来存储每个节点的最后的污染指数
优缺点：博主java的写法是最简单的很适合新手，没有利用什么数据结构，利用的是链式前向星，但是写起来相对比较麻烦，仅供java新手参考