对应题目

luogu3385

Bellman-ford

relax n轮 判断第n+1轮是否还可以relax 可以说明有负环

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
#include<queue>
#include<iostream>
#include<stack>
#include<vector>
#include<bitset>
#include<set>
#include<map>
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define clr(a,x) memset(a,x,sizeof(a))
#define inf (0x7fffffff)
typedef long long ll;
using namespace std;
int readint(){
    int ans = 0,f = 1;
    char c = getchar();
    while(!isdigit(c)){
        if(c == '-') f = -1;
        c = getchar();
    }
    while(isdigit(c)){
        ans = ans*10 + c - '0';
        c = getchar();
    }
    return f*ans;
}
char num_print[12];
void printint(int x){
    if(x == 0){
        putchar('0');
        return;
    }
    int tmp = x > 0 ? x : -x;
    if(x < 0) putchar('-');
    int cnt = 0;
    while(tmp > 0){
        num_print[cnt++] = tmp%10 + '0';
        tmp/=10;
    }
    while(cnt--) putchar(num_print[cnt]);
}
const int maxn = 2e3+9,maxm = 1e4+9;
struct edge{
    int v,w;
    edge*next;
    edge(int V = 0,int W = 0):v(V),w(W){}
};
edge E[maxm],*pt = E,*fir[maxn];
int n,m;
int d[maxn];
void addedge(int u,int v,int w){
    pt->v = v;
    pt->w = w;
    pt->next = fir[u];
    fir[u] = pt++;
}
void resetedge(){
    pt = E;
    memset(fir,0,sizeof(fir));
}
bool bellman_ford(){
    for(int i = 2; i <= n; i ++)
        d[i] = inf;
    d[1] = 0;
    for(int i = 0; i <= n; i ++)
        for(int x = 1; x <= n; x ++)
            for(edge*e = fir[x]; e != NULL; e = e->next)
                if(d[x] != inf && d[e->v] > d[x] + e->w){
                    if(i == n) return 1;
                    d[e->v] = d[x] + e->w;
                }
    return 0;
}
int main(){
    //std::ios::sync_with_stdio(false);
    //freopen("#test.in","r",stdin);
    //freopen("#test.out","w",stdout);
    int T = readint();
    while(T--){
        resetedge();
        n = readint();
        m = readint();
        while(m--){
            int u = readint(),v = readint(),w = readint();
            addedge(u,v,w);
            if(w >= 0) addedge(v,u,w);
        }
        puts(bellman_ford() ? "YES" : "NO");
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}

SPFA

原理一样 判断一个点是否入列n次以上
多组数据reset要做好

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
#include<queue>
#include<iostream>
#include<stack>
#include<vector>
#include<bitset>
#include<set>
#include<map>
#define rep(i,l,r) for(int i=(l);i<=(r);i++)
#define clr(a,x) memset(a,x,sizeof(a))
#define inf (0x7fffffff)
typedef long long ll;
using namespace std;
int readint(){
    int ans = 0,f = 1;
    char c = getchar();
    while(!isdigit(c)){
        if(c == '-') f = -1;
        c = getchar();
    }
    while(isdigit(c)){
        ans = ans*10 + c - '0';
        c = getchar();
    }
    return f*ans;
}
char num_print[12];
void printint(int x){
    if(x == 0){
        putchar('0');
        return;
    }
    int tmp = x > 0 ? x : -x;
    if(x < 0) putchar('-');
    int cnt = 0;
    while(tmp > 0){
        num_print[cnt++] = tmp%10 + '0';
        tmp/=10;
    }
    while(cnt--) putchar(num_print[cnt]);
}
const int maxn = 2e3+9,maxm = 1e4+9;
struct edge{
    int v,w;
    edge*next;
    edge(int V = 0,int W = 0):v(V),w(W){}
};
edge E[maxm],*pt = E,*fir[maxn];
int n,m;
int d[maxn];
queue<int>Q;
bool p[maxn];
int cnt[maxn];
void addedge(int u,int v,int w){
    pt->v = v;
    pt->w = w;
    pt->next = fir[u];
    fir[u] = pt++;
}
void resetedge(){
    pt = E;
    while(!Q.empty()) Q.pop();
    memset(d,0,sizeof(d));
    memset(p,0,sizeof(p));
    memset(fir,0,sizeof(fir));
    memset(cnt,0,sizeof(cnt));
}
bool spfa(){
    for(int i = 2; i <= n; i ++)
        d[i] = inf;
    d[1] = 0;
    p[1] = 1;
    cnt[1] = 1;
    Q.push(1);
    while(!Q.empty()){
        int x = Q.front();
        Q.pop();
        p[x] = 0;
        for(edge*e = fir[x]; e != NULL; e = e->next){
            if(d[e->v] > d[x] + e->w){
                d[e->v] = d[x] + e->w;
                cnt[e->v] ++;
                if(cnt[e->v] > n) return 1;
                if(!p[e->v]){
                    Q.push(e->v);
                    p[e->v] = 1;
                }
            }
        }
    }
    return 0;
}
int main(){
    //std::ios::sync_with_stdio(false);
    //freopen("#test.in","r",stdin);
    //freopen("#test.out","w",stdout);
    int T = readint();
    while(T--){
        resetedge();
        n = readint();
        m = readint();
        while(m--){
            int u = readint(),v = readint(),w = readint();
            addedge(u,v,w);
            if(w >= 0) addedge(v,u,w);
        }
        puts(spfa() ? "YES" : "NO");
    }
    //fclose(stdin);
    //fclose(stdout);
    return 0;
}
Last modification:April 30th, 2020 at 12:59 am
如果觉得我的文章对你有用,请随意赞赏