洛谷-P3385 [模板] 负环¶

洛谷-P3385 [模板] 负环¶

题目描述¶

暴力枚举 / SPFA / Bellman-ford / 奇怪的贪心 / 超神搜索

寻找一个从顶点 11 所能到达的负环，负环定义为：一个边权之和为负的环。

输入格式¶

本题有多组数据

第一行一个正整数 TT 表示数据组数，对于每组数据：

第一行两个正整数 N, MN,M，表示图有 NN 个顶点，MM 条边

接下来 MM 行，每行三个整数 a, b, wa,b,w，表示a \rightarrow ba→b 有一条权值为 ww 的边（若 w<0w<0 则为单向，否则双向）。

输出格式¶

共 TT 行。对于每组数据，存在负环则输出一行YE5(不含引号)，否则输出一行N0(不含引号)。

输入输出样例¶

输入 #1

输出 #1

N0
YE5

说明/提示¶

n\le 2000n≤2000，m\le 3000m≤3000，-10000\le w \le 10000−10000≤w≤10000，T\le 10T≤10。

建议复制输出格式中的字符串。

本题数据感谢 @negiizhao 的精心构造，请不要使用玄学算法。

本题数据有更新。

#include <iostream>
#include <vector>
#include <cmath>
#include <string>
#include <climits>
#include <cstdio>
#include <queue>
#include <algorithm>

using namespace std;

const int INF = 0X0ffffff;

struct Node
{
    int from, to, cost;
};

int vertexNum = 2005, edgeNum = 6005;
vector<int> d(vertexNum, INT_MAX); //最短距离
vector<Node> es(edgeNum); //边

bool findNegativeCircle(int s)
{
    fill(d.begin(), d.end(), INT_MAX);
    d[s] = 0;

    for (int i = 0; i < vertexNum; ++i) {
        for (int j = 1; j <= edgeNum; ++j) {
            if (d[es[j].from] != INT_MAX && d[es[j].to] > d[es[j].from] + es[j].cost) {
                d[es[j].to] = d[es[j].from] + es[j].cost;
                if (i == vertexNum - 1) return true;
            }
        }
    }

    return false;
}

int main()
{
    std::ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int caseNum;
    cin >> caseNum;
    while (caseNum--) {
        cin >> vertexNum >> edgeNum;
        for (int i = 1; i <= edgeNum; ++i) {
            cin >> es[i].from >> es[i].to >> es[i].cost;
            if (es[i].cost >= 0) {
                ++edgeNum;
                ++i;
                es[i].from = es[i - 1].to;
                es[i].to = es[i - 1].from;
                es[i].cost = es[i - 1].cost;
            }
        }
        if (findNegativeCircle(1)) cout << "YE5" << endl;
        else cout << "N0" << endl;
    }

    return 0;
}

这道题目核心考察是负环的检测，坑点有：

输出结果是YE5注意是数字5，N0是数字0（最初提交进去发现就过了两个，其他全是WA，在于没有仔细看输出的要求）
权值非负，是双向边，那么边的数量是增加的，所以最初给的边的数量是3000，但是很可能给的所有边的权重都是非负，那么就可能是6000条边，不然会出现RE（用邻接表就不会出现这种问题），所以空间开的大一点比较好。

上面这种用Bellman-Ford解题的方法，和《挑战程序设计竞赛》里不一样，如果初始d内的值都是0会有一个测试用例过不去。