我宽嫂就是没思路 爆零 被FST 也不会刷你们洛谷一点水题

真香

懵逼的 题目

传送至 某谷

扯淡的 题解

判断负环…一般用到的方法主要就是SPFA…SPFA有两样写法,你知道么

  1. BFS-SPFA: 直接记录每一个节点入队的次数, 如果cnt[b[i].to]大于n就可以直接退出了, 然而期望是$\mathrm O(nm)$的, 这个丧心病狂的题就别想了…
  2. DFS-SPFA: 只记录dis和当前节点是否在本次DFS中被访问过, 有点类似于tarjan(都是dfs), 只不过要求的是负环…

你以为这样就结束了?

恭喜, 你已经有了20分了…

优化

  1. 如果b[i].to在本次DFS中被访问过了, 不必判断dis是否为负(?) 因为如果绕了一圈又回到这个点, 而dis变小了, 说明绕的这一圈总边权一定为负(?)
  2. 初始化dis的时候不必初始化为0x7f直接初始化为0即可, 因为是找负环(?)

感觉上面的优化都挺不靠谱的…但是反正Luogu的数据能过…

沙茶的 代码

我很想知道最优解那些人是怎么卡的….

// luogu-judger-enable-o2
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <queue>
#include <stack>
#define MAXN (200000 + 5)
#define MAXM (200000 + 5)
#define INF (0x7ffffff)
using namespace std;
struct edg
{
    int from, to, next, cost;
}b[MAXM << 1];
int g[MAXN], cntb, ans, dis[MAXN];
bool vis[MAXN];
char pans[2][5] = {"N0", "YE5"};
int n, m;
void adn(int from, int to, int cost)
{
    b[++cntb].next = g[from];
    b[cntb].from = from;
    b[cntb].to = to;
    b[cntb].cost = cost;
    g[from] = cntb;
}
void spfa(int);
int main()
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        memset(dis, 0, sizeof(dis));
        memset(vis, false, sizeof(vis));
        memset(g, 0, sizeof(g));
        cntb = 0;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= m; i++)
        {
            int srx, sry, srz;
            scanf("%d%d%d", &srx, &sry, &srz);
            adn(srx, sry, srz);
            if (srz > 0)
                adn(sry, srx, srz);
        }
        ans = 0;
        for (int i = 1; i <= n; i++)
            if (!vis[i])
            {
                dis[i] = 0, spfa(i);
                if (ans)    break;
            }
        printf("%s\n", pans[ans]);
    }
    return 0;
}
void spfa(int dq)
{
    vis[dq] = true;
    for (int i = g[dq]; i; i = b[i].next)
    {
        if (dis[b[i].to] > dis[dq] + b[i].cost)
        {
            dis[b[i].to] = dis[dq] + b[i].cost;
            if (vis[b[i].to])
            {
                ans = 1;
                return ;
            }
            else
                spfa(b[i].to);
            if (ans)
                return ;
        }
    }
    vis[dq] = false;
}

/*
2
3 4
1 2 2
1 3 4
2 3 1
3 1 -3
3 3
1 2 3
2 3 4
3 1 -8
*/

By 失去梦想的 Cansult