头像

大十三


访客:300

离线:26天前


活动打卡代码 AcWing 852. spfa判断负环

大十三
2个月前

```
算法分析
使用spfa算法解决是否存在负环问题

1、dist[x] 记录当前1到x的最短距离

2、cnt[x] 记录当前最短路的边数,初始每个点到1号点的距离为0,只要他能再走n步,即cnt[x] >= n,则表示该图中一定存在负环,由于从1到x至少经过n条边时,则说明图中至少有n + 1个点,表示一定有点是重复使用

3、若dist[j] > dist[t] + w[i],则表示从t点走到j点能够让权值变少,因此进行对该点j进行更新,并且对应cnt[j] = cnt[t] + 1,往前走一步

注意:该题是判断是否存在负环,并非判断是否存在从1开始的负环,因此需要将所有的点都加入队列中,更新周围的点

时间复杂度 一般:O(m)O(m) 最坏:O(nm)O(nm)
参考文献
Java 代码
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
static int n;
static int m;
static int N = 2010;
static int M = 10010;
static int[] h = new int[N];
static int[] e = new int[M];
static int[] ne = new int[M];
static int[] w = new int[M];
static int idx = 0;
static int[] dist = new int[N];//记录当前1到x的最短距离
static int[] cnt = new int[N];//从1到点到x经过的边数
static boolean[] st = new boolean[N];

public static void add(int a,int b,int c)
{
    e[idx] = b;
    w[idx] = c;
    ne[idx] = h[a];
    h[a] = idx ++;

}
public static boolean spfa()
{
    Queue<Integer> queue = new LinkedList<Integer>();
    //将所有点进入队列
    for(int i = 1;i <= n;i++)
    {
        queue.add(i);
        st[i] = true;
    }
    while(!queue.isEmpty())
    {
        int t = queue.poll();
        st[t] = false;
        for(int i = h[t]; i != -1;i = ne[i])
        {
            int j = e[i];
            if(dist[j] > dist[t] + w[i])
            {
                dist[j] = dist[t] + w[i];
                cnt[j] = cnt[t] + 1;

                if(cnt[j] >= n) return true;
                if(!st[j])
                {
                    queue.add(j);
                    st[j] = true;
                }


            }
        }
    }
    return false;
}
public static void main(String[] args) throws IOException {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    String[] str1 = reader.readLine().split(" ");
    n = Integer.parseInt(str1[0]);
    m = Integer.parseInt(str1[1]);
    Arrays.fill(h, -1);
    while(m -- > 0)
    {
        String[] str2 = reader.readLine().split(" ");
        int a = Integer.parseInt(str2[0]);
        int b = Integer.parseInt(str2[1]);
        int c = Integer.parseInt(str2[2]);
        add(a,b,c);
    }
    if(spfa()) System.out.println("Yes");
    else System.out.println("No");
}

}



活动打卡代码 AcWing 851. spfa求最短路

大十三
2个月前
#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

const int N = 1e6 + 10;

int h[N], e[N], ne[N], W[N], idx; //邻接表存储所有边
int n; // the num of point
int m; // the num of the lines
int dist[N]; //存储每个点到一号点的最小距离
bool st[N];//存储每个点是否在队列中
//add one line a -> b 
void add(int a, int v, int w) {
    e[idx] = v;
    ne[idx] = h[a];
    W[idx] = w;
    h[a] = idx ++;
}


int spfa() {
    memset(dist, 0x3f , sizeof dist);

    dist[1] = 0;
    st[1] = false;

    queue<int>q;
    q.push(1);
    while(!q.empty()) {
        auto t = q.front();
        q.pop();

        for(int i = h[t]; i !=-1; i = ne[i] ) {
            auto j = e[i];
            if(dist[j] > (dist[t] + W[i])) {
                dist[j] = dist[t] + W[i];
                if(!st[j]) {
                    q.push(j);
                    st[j] = true;
                }
            }
        }

    }

    if(dist[n] == 0x3f3f3f3f) return -1;
    else return dist[n];

}

int main() {
    cin >> n >>m;
    memset(h, -1, sizeof h);

    while(m--) {
        int x, y, z;
        cin >> x >> y >> z;
        add(x, y, z);
    }
    auto v = spfa();
    if(v == -1) cout <<"impossible" << endl;
    else cout << v << endl;
}



大十三
2个月前
class Solution {
public:
    int strToInt(string str) {

        int res = 0;
         if(str.size() == 0) return res;
        int i = 0, j = str.size() -1;
        while(i <= j && str[i] == ' ') i ++;
        if((str[i] <= '0' || str[i] >= '9') && (str[i] != '-' && str[i] != '+') ) return res;
        while(i <= j && (str[j] <= '0' || str[j] >= '9')) j --;
        str = str.substr(i, j - i + 1 );


        bool bMinus = false;
        if(str[0] == '-' )
        {
          bMinus = true;;
           str = str.substr(1);

        }
        else if(str[0] == '+' )
        {

           str = str.substr(1);

        }

        long long sum = 0;
        for(auto c : str) sum *= 10, sum += (c - '0');
        if(bMinus) sum *= (-1);
        if(sum > INT_MAX) res = INT_MAX;
        else if(sum < INT_MIN) res = INT_MIN;
        else res = sum;

        return res;

    }
};


活动打卡代码 AcWing 86. 构建乘积数组

大十三
2个月前
class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        int n = A.size();
        vector<int> res(n);
        for(int i = 0, mul = 1; i < n; i ++) {
            res[i] = mul;
            mul = A[i] * mul;
        }

        for(int i = n -1, mul = 1; i >=0; i --) {
            res[i] = res[i] *mul;
            mul = A[i] * mul;
        }
        return res;
    }
};



大十三
2个月前
class Solution {
public:
    int add(int num1, int num2){
        while(num2 != 0 ){
            int sum = num1 ^ num2;
            int carry = (num1 & num2) << 1; // 加括号
            num1 = sum;
            num2 = carry;
        }
        return num1;
    }
};



大十三
2个月前
class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        int n = A.size();
        vector<int> res(n);
        for(int i = 0, mul = 1; i < n; i ++) {
            res[i] = mul;
            mul = A[i] * mul;
        }

        for(int i = n -1, mul = 1; i >=0; i --) {
            res[i] = res[i] *mul;
            mul = A[i] * mul;
        }
        return res;
    }
};



大十三
2个月前
class Solution {
public:
    int add(int num1, int num2){
        while(num2 != 0 ){
            int sum = num1 ^ num2;
            int carry = (num1 & num2) << 1; // 加括号
            num1 = sum;
            num2 = carry;
        }
        return num1;
    }
};


活动打卡代码 AcWing 84. 求1+2+…+n

大十三
2个月前
class Solution {
public:
    int getSum(int n) {
        int res = n;
        (n>0) && (res += getSum(n-1));//利用短路运算终止递归
        return res;
    }
};



大十三
2个月前
class Solution {
public:
    int maxDiff(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        int res = 0;
        int minValue = nums[0];
        for(int i = 1; i < nums.size(); i ++) {
            res = max(nums[i] - minValue, res);
            minValue = min(nums[i], minValue);
        }

        return res;
    }
};



大十三
2个月前
//圆圈中最后剩下的数字
//递归
class Solution {
public:
    int lastRemaining(int n, int m){
        if(n==1)
            return 0;
        else
            return (lastRemaining(n-1,m)+m)%n;
    }
};

#include <list>
class Solution {
public:
    int lastRemaining(int n, int m){
        list<int> nums;
        for (int i = 0; i < n; ++i) nums.push_back(i);
        auto it = nums.begin();
        int k = m - 1;
        while (nums.size() > 1){
            while (k--){
                it++;
                if (it == nums.end()) it = nums.begin();//别迭代器移到开头实现模拟环形列表
            }
            it = nums.erase(it);//删除第m个元素
            if (it == nums.end()) it = nums.begin();
            k = m - 1;
        }
        return nums.front();
    }
};