AcWing 852. spfa判断负环

历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

AcWing 852. spfa判断负环原题链接简单

作者：

Bug-Free , 2021-03-29 23:52:23 , 所有人可见 , 阅读 7281

40

14

代码

#include <cstring>
#include <iostream>
#include <queue>

using namespace std;

const int N = 2e3 + 10, M = 1e4 + 10;

int n, m;
int head[N], e[M], ne[M], w[M], idx;
bool st[N];
int dist[N];
int cnt[N]; //cnt[x] 表示 当前从1-x的最短路的边数

void add(int a, int b, int c)
{
    e[idx] = b;
    ne[idx] = head[a];
    w[idx] = c;
    head[a] = idx++;
}

bool spfa(){
    // 这里不需要初始化dist数组为 正无穷/初始化的原因是， 如果存在负环， 那么dist不管初始化为多少， 都会被更新

    queue<int> q;

    //不仅仅是1了， 因为点1可能到不了有负环的点， 因此把所有点都加入队列
    for(int i=1;i<=n;i++){
        q.push(i);
        st[i]=true;
    }

    while(q.size()){
        int t = q.front();
        q.pop();
        st[t]=false;
        for(int i = head[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]){
                    q.push(j);
                    st[j]=true;
                }
            }
        }
    }
    return false;
}

int main()
{
    cin >> n >> m;
    memset(head, -1, sizeof head);
    for (int i = 0; i < m; i++) {
        int a, b, c;
        cin >> a >> b >> c;
        add(a, b, c);
    }

    if (spfa()) {
        cout << "Yes" << endl;
    }
    else {
        cout << "No" << endl;
    }
    return 0;
}

14 评论

yhm233 2022-10-21 20:55

请问不需要 memset(dist, 0x3f, sizeof dist); 初始化可不可以理解为因为本题需要判断负环，如果存在负环，那么就会导致松弛的时候，w[i] < 0，于是导致 dist 更新；而如果不存在负环，那么这种情况 dis 到底更不更新无所谓（其实dis不会更新吧，因为没有对 dis 初始化为无穷的话默认就是0, 0和一个正数比较肯定不需要松弛）

今日臭明日香 7个月前

#include [HTML_REMOVED]
#include [HTML_REMOVED]
#include [HTML_REMOVED]

using namespace std;

const int N = 10010;
int w[N], h[N], e[N], ne[N], idx;

int d[N], cnt[N];
bool st[N];
int q[N];

int n, m;

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

bool spfa() {
int hh = 0, tt = -1;

for (int i = 1; i <= n; i++) {
    q[++tt] = i;
    st[i] = true;
}

while (hh <= tt) {
    int t = q[hh++];
    st[t] = false;

    for (int i = h[t]; i != -1; i = ne[i]) {
        int b = e[i], c = w[i];

        if (d[b] > d[t] + c) {
            d[b] = d[t] + c;
            cnt[b] = cnt[t] + 1;
            if (cnt[b] >= n) return true;
            if (!st[b]) {
                q[++tt] = b;
                st[b] = true;
            }
        }
    }
}

return false;

}

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

while (m--) {
    int a, b, w;
    cin >> a >> b >> w;
    add(a, b, w);
}

bool res = spfa();

if (!res) {
    cout << "No" << endl;
} else {
    cout << "Yes" << endl;
}

return 0;

}
我在这里使用了手写队列却ac不了，有大佬看看为什么吗…我直接用的上一题的模版

Krona 6个月前

你这个手写队列初始化给的空间有问题，不应该是节点数N，而应该是N*M，因为要注意到手写队列的tt和hh会一直右移，其需要的空间为可能通过的元素的总和。

#include<iostream>
#include<cstring>
#include<queue>

using namespace std;
const int N=2e3+10,M=1e4+10;
int n,m;
int h[N],e[M],ne[M],w[M],idx;
bool st[N];
int dist[N];
int cnt[N];
int q[N*M],hh=0,tt=-1;
void add(int a,int b,int c){
    e[idx]=b;
    ne[idx]=h[a];
    w[idx]=c;
    h[a]=idx++;
}
bool spfa(){
    for(int i=1;i<=n;i++){
        q[++tt]=i;
        st[i]=true;
    }
    while(hh<=tt){
        int t=q[hh++];
        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])continue;
                q[++tt]=j;
                st[j]=true;
            }
        }
    }
    return false;
}

int main(){
    ios::sync_with_stdio(false);
    cin>>n>>m;
    memset(h,-1,sizeof h);
    memset(dist,0x3f,sizeof dist);
    for(int i=0;i<m;i++){
        int a,b,c;
        cin>>a>>b>>c;
        add(a,b,c);
    }
    if(spfa())cout<<"Yes"<<endl;
    else cout<<"No"<<endl;

    return 0;
}