POJ 3259 Wormholes ( SPFA判断负环 && 思维 )

题意 : 给出 N 个点,以及 M 条双向路,每一条路的权值代表你在这条路上到达终点需要那么时间,接下来给出 W 个虫洞,虫洞给出的形式为 A B C 代表能将你从 A 送到 B 点,并且回到 C 个时间点之前,也就是时光倒流了 C 个时间并且此时你在 B 点,现在问你是否能够在图上的这些点中走,使得在某一个点刚好碰到之前的自己文章地址https://www.yii666.com/article/756149.html网址:yii666.com文章来源地址:https://www.yii666.com/article/756149.html

分析 : 冷静分析一下,只要是有负权回路的某一条边属于虫洞的,那么肯定是能在这个环上一直绕,直到遇到之前的自己,如果将虫洞看作一条负权边的话,那么问题就变成了只要存在负环,那么肯定是能够通过负环回路达到见到过去的自己这种操作的,用SPFA判一下就OK了!最好自己好好分析一下,为什么只要环上有虫洞就能达到目的,这个证明是很重要的!文章来源地址https://www.yii666.com/article/756149.html网址:yii666.com<

#include <iostream>
#include <cstdio>
#include <cmath>
#include <queue>
#include <string.h>
using namespace std;

const int INF=0x3f3f3f3f;
;

struct EdgeNode{ int v, w, nxt; };
EdgeNode Edge[maxn*maxn];
bool vis[maxn];
int Head[maxn], Dis[maxn], cnt;
int N, M;
int PushCnt[maxn]; ///记录每一个节点的入队次数、方便判断负环

inline void init()
{
    ; i<=N; i++)
        PushCnt[i] = ,
        Head[i] = -,
        Dis[i]  = INF,
        vis[i]  = false;
    cnt = ;
}

inline void AddEdge(int from, int to, int weight)
{
    Edge[cnt].w = weight;
    Edge[cnt].v = to;
    Edge[cnt].nxt = Head[from];
    Head[from] = cnt++;
}

bool SPFA(int st)///若要判断负环、改为 bool
{
    deque<int> que;
    que.push_back(st);
    vis[st]=true;
    Dis[st]=;
    while (!que.empty())
    {
        int T=que.front(); que.pop_front();
        vis[T]=false;
        ; i=Edge[i].nxt)
        {
            int v=Edge[i].v;
            int w=Edge[i].w;
            if (Dis[v]>Dis[T]+w){
                Dis[v]=Dis[T]+w;
                if (!vis[v]){
                    if(++PushCnt[v] > N) return false; //有负环
                    vis[v]=true;
                    if(!que.empty() && Dis[v] < Dis[que.front()]) que.push_front(v);
                    else que.push_back(v);
                }
            }
        }
    }
    return true;
}

int main(void)
{
    int nCase, W;
    scanf("%d", &nCase);
    while(nCase--){
        scanf("%d %d %d", &N, &M, &W);
        init();
        int from, to, weight;
        ; i<M; i++){
            scanf("%d %d %d", &from, &to, &weight);
            AddEdge(from, to, weight);
            AddEdge(to, from, weight);
        }
        ; i<W; i++){
            scanf("%d %d %d", &from, &to, &weight);
            AddEdge(from, to, -weight);
        }
        SPFA()?puts("NO"):puts("YES");
    }
    ;
}

版权声明:本文内容来源于网络,版权归原作者所有,此博客不拥有其著作权,亦不承担相应法律责任。文本页已经标记具体来源原文地址,请点击原文查看来源网址,站内文章以及资源内容站长不承诺其正确性,如侵犯了您的权益,请联系站长如有侵权请联系站长,将立刻删除

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信图片_20190322181744_03.jpg

微信扫一扫打赏

请作者喝杯咖啡吧~

支付宝扫一扫领取红包,优惠每天领

二维码1

zhifubaohongbao.png

二维码2

zhifubaohongbao2.png