首页 > 其他分享 >洛谷 P3385 【模板】负环

洛谷 P3385 【模板】负环

时间:2024-09-24 22:51:41浏览次数:8  
标签:count 洛谷 point int res 负环 P3385 edge

题目链接:P3385 【模板】负环



思路

       负环模版题,套一个SPFA板子,判断一下每个节点进入队列的次数,当进入队列的次数大于等于n次时,表示当前节点迭代次数超过了n - 1次,即为存在负环。


代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 0x3f3f3f3f;
const int N = 1e5 + 10;
struct List {
  ll head[N], edge[N], next[N], dis[N], cnt, res[N];
  // 判断负环
  int count[N], flag;
  bool vis[N];
  // 处理邻接表
  void add(int x, int y, int distance) {
    next[++cnt] = head[x];
    head[x] = cnt;
    edge[cnt] = y;
    dis[cnt] = distance;
  }
  void SPFA(int start, int n) {
    memset(count, 0, sizeof count);
    memset(vis, 0, sizeof vis);
    memset(res, 0x3f, sizeof res);
    queue<int> q;
    q.push(start);
    res[start] = 0;
    vis[start] = true;
    while (!q.empty()) {
      int point = q.front();
      q.pop();
      vis[point] = false;
      for (int i = head[point]; i; i = next[i]) {
        if (res[edge[i]] > dis[i] + res[point]) {
          res[edge[i]] = dis[i] + res[point];
          count[edge[i]] = count[point] + 1;
          if (count[edge[i]] >= n) {
            cout << "YES" << endl;
            flag = 1;
            return;
          }
          if (!vis[edge[i]]) {
            q.push(edge[i]);
            vis[edge[i]] = true;
          }
        }
      }
    }
  }
  void adjacentList() {
    memset(head, 0, sizeof head);
    cnt = 0, flag = 0;
    int n, m, s;
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
      ll u, v, w;
      cin >> u >> v >> w;
      add(u, v, w);
      if (w >= 0)
        add(v, u, w);
    }
    SPFA(1, n);

    if (flag == false) {
      cout << "NO" << endl;
    }
    // cout << res[n] << endl;
  }
};

int main() {
  int t;
  cin >> t;
  List list;
  while (t--) {
    list.adjacentList();
  }
  return 0;
}

标签:count,洛谷,point,int,res,负环,P3385,edge
From: https://www.cnblogs.com/againss/p/18430252

相关文章

  • 洛谷题单指南-分治与倍增-P3509 [POI2010] ZAB-Frog
    原题链接:https://www.luogu.com.cn/problem/P3509题意解读:n个点,每个点上有一只青蛙每次跳到距离自己第k近的点,m次之后跳到哪个点。解题思路:1、计算距离每个点第k近的点,存入ne[N]给定一个点i,距离i第k近的点一定在长度为k+1个点的窗口内,窗口包括i并且,第k近的点只能是左端点或者......
  • 【洛谷】P2261 [CQOI2007] 余数求和 的题解
    【洛谷】P2261[CQOI2007]余数求和的题解洛谷传送门题解这还是蓝题,这还是省选qaq题目看着很简单,但是真的很考验思路,思路对了,代码不到555分钟写完。刚开始做的时......
  • bfs与优先队列 [NOIP2017 普及组] 棋盘————洛谷p3956
    [NOIP2017普及组]棋盘题目背景NOIP2017普及组T3题目描述有一个\(m\timesm\)的棋盘,棋盘上每一个格子可能是红色、黄色或没有任何颜色的。你现在要从棋盘的最左上角走到棋盘的最右下角。任何一个时刻,你所站在的位置必须是有颜色的(不能是无色的),你只能向上、下、左、右......
  • 【洛谷】P10417 [蓝桥杯 2023 国 A] 第 K 小的和 的题解
    【洛谷】P10417[蓝桥杯2023国A]第K小的和的题解题目传送门题解CSP-S1补全程序,致敬全A的答案,和神奇的预言家。写一下这篇的题解说不定能加CSP2024的RP代码#include<bits/stdc++.h>#definelowbit(x)x&(-x)#defineendl"\n"usingnamespacestd......
  • 洛谷P5683 [CSP-J2019 江西] 道路拆除
    立下flag:今天一定AC这道题!题目意思:思路:然而并没有分。。输出-1,祈求CCF的施舍(30%的数据,有\(s_1=s_2\)求1号点到\(s_1\)最短路,再计算不需要的路径。SPFA,启动!#include<bits/stdc++.h>usingnamespacestd;constintmaxn=3010;constintmaxm=3010;intm,n;i......
  • BFS 马的遍历————洛谷p1443
    马的遍历题目描述有一个\(n\timesm\)的棋盘,在某个点\((x,y)\)上有一个马,要求你计算出马到达棋盘上任意一个点最少要走几步。输入格式输入只有一行四个整数,分别为\(n,m,x,y\)。输出格式一个\(n\timesm\)的矩阵,代表马到达某个点最少要走几步(不能到达则输出\(-......
  • 洛谷 P1093 [NOIP2007 普及组] 奖学金
    [NOIP2007普及组]奖学金题目背景NOIP2007普及组T1题目描述某小学最近得到了一笔赞助,打算拿出其中一部分为学习成绩优秀的前555名学生发奖学金。期末,每个学生都......
  • BFS 颜色填涂———洛谷p1162
    填涂颜色题目描述由数字\(0\)组成的方阵中,有一任意形状的由数字\(1\)构成的闭合圈。现要求把闭合圈内的所有空间都填写成\(2\)。例如:\(6\times6\)的方阵(\(n=6\)),涂色前和涂色后的方阵如下:如果从某个\(0\)出发,只向上下左右\(4\)个方向移动且仅经过其他\(0\)的情况下......
  • dfs 油滴拓展——洛谷p1378
    油滴扩展题目描述在一个长方形框子里,最多有\(N\)个相异的点,在其中任何一个点上放一个很小的油滴,那么这个油滴会一直扩展,直到接触到其他油滴或者框子的边界。必须等一个油滴扩展完毕才能放置下一个油滴。那么应该按照怎样的顺序在这\(N\)个点上放置油滴,才能使放置完毕后所有......
  • 【洛谷】P3128 [USACO15DEC] Max Flow P 的题解
    【洛谷】P3128[USACO15DEC]MaxFlowP的题解题目传送门题解谔谔,LCA+++树上差分,差点就被难倒了qaq今天就是CSP初赛了,祝大家也祝我自己rp++!!!其实是一道树上差......