下雪了

洛谷P3385 -【模板】负环(SPFA)

SPFA判断负环的模板题,利用BFS来遍历并标记入队的次数,如果大于n次则说明出现了负环。

AC代码:

#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<string>
#include<vector>
#include<cstdio>
#include<stack>
#include<cmath>
#include<ctime>
#include<queue>
#include<deque>
#include<list>
#include<map>
#define ffor(i, a, b) for(int i = a; i <= b; i++)
#define rfor(i, a, b) for(int i = a; i >= b; i--)
#define mes(a,b) memset(a, b, sizeof(a))
#define cos(x) cos(x*PI/180.0)
#define sin(x) sin(x*PI/180.0)
#define stop system("pause")
#define see(s,x) cout<<(s)<<'='<<(x)<<endl
#define IMAX 0x7fffffff
#define PI 3.141592654
#define INF 0x3f3f3f3f
#define eps 1e-6
#define lowbit(x) (x&(-x))
typedef long long ll;
const ll mod = (ll)1e9 + 7;
ll max(ll a, ll b) { return(a > b) ? a : b; }
ll min(ll a, ll b) { return(a < b) ? a : b; }
using namespace std;

struct unit
{
    int to;
    int w;
    unit() {};
    unit(int a, int b) :to(a), w(b) {};
};

vector<unit> G[3005];
int dis[3005];
int cnt[3005];
bool v[3005];

bool spfa(int s,int n)
{
    dis[s] = 0;
    queue<int> q;
    q.push(s);
    cnt[s]++;
    while (!q.empty())
    {
        int f = q.front();
        q.pop();
        v[f] = false;
        for (vector<unit>::iterator it = G[f].begin(); it != G[f].end(); it++)
        {
            unit u = *it;
            if (dis[f] + u.w < dis[u.to])
            {
                dis[u.to] = dis[f] + u.w;
                if (!v[u.to])
                {
                    q.push(u.to);
                    v[u.to] = true;
                    cnt[u.to]++;
                    if (cnt[u.to] > n)
                        return true;
                }
            }
        }
    }
    return false;
}

int main()
{
    int T;
    cin >> T;
    while (T--)
    {
        int n, m;
        cin >> n >> m;
        ffor(i, 1, n)
        {
            cnt[i] = 0;
            v[i] = false;
            dis[i] = IMAX;
            G[i].clear();
        }
        ffor(i, 1, m)
        {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            if (z >= 0)
            {
                G[x].push_back(unit(y, z));
                G[y].push_back(unit(x, z));
            }
            else G[x].push_back(unit(y, z));
        }
        if (spfa(1, n))
            cout << "YE5" << endl;
        else cout << "N0" << endl;
    }
}

 


Add Your Comment

* Indicates Required Field

Your email address will not be published.

*