首页 > 代码库 > UVA 558 Wormholes

UVA 558 Wormholes

利用SPFA判负环。如果一个节点出队N次有负环这里记录一下

#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}int cnt[1010];bool inq[1010];int d[1010];int w[1010][1010],N,M;vector<int>G[1010];queue<int>q;bool SPFA(){    memset(cnt,0,sizeof(cnt));    memset(inq,false,sizeof(inq));    memset(d,0x3f,sizeof(d));    while (!q.empty()) q.pop();    q.push(0); cnt[0]++;    inq[0] = true; d[0] = 0;    while (!q.empty())    {        int u = q.front(); q.pop();        inq[u] = false;        for (int i = 0; i < (int)G[u].size(); i++)        {            int v = G[u][i];            if (d[v] > d[u] + w[u][v])            {                d[v] = d[u] + w[u][v];                if (!inq[v])                {                    inq[v] = true;                    cnt[v]++;                    if (cnt[v] >= N) return true;                    q.push(v);                }            }        }    }    return false;}int main(){    //freopen("sample.txt","r",stdin);    int T;    scanf("%d",&T);    while (T--)    {        scanf("%d%d",&N,&M);        for (int i = 0; i < 1010; i++) G[i].clear();        while (M--)        {            int u,v,we;            scanf("%d%d%d",&u,&v,&we);            G[u].push_back(v);            w[u][v] =  we;        }        if (SPFA()) puts("possible");        else puts("not possible");    }    return 0;}

 

UVA 558 Wormholes