当前位置:网站首页>AcWing 904. 虫洞 题解(spfa求负环)
AcWing 904. 虫洞 题解(spfa求负环)
2022-07-06 18:00:00 【乔大先生】
AcWing 904. 虫洞
负环就是图中存在的权值之和为负数的环,如果图中存在负环,则农夫一定能返回起点,反之一定不能,所以这是一个裸的求负环的题目。用spfa记录最短路上的边的数量,如果某条路径上边的数量大于等于n,则可以认定这条路上存在负环,返回true即可,反之返回false
#include<bits/stdc++.h>
using namespace std;
const int N = 520, M = 5210;
int T, n, m1, m2;
int h[N], ne[M], e[M], w[M], idx;
int st[N];
int dist[N]; //最短距离记录数组
int cnt[N]; //记录最短距离的边数
void add(int a, int b, int c){
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx ++ ;
}
bool spfa(){
//判断负环
memset(dist, 0, sizeof dist);
memset(st, 0, sizeof st);
memset(cnt, 0, sizeof cnt);
queue<int>q;
for(int i = 1; i <= n; i ++ ){
q.push(i);
st[i] = true;
}
while(q.size()){
int t = q.front();
q.pop();
st[t] = false;
for(int i = h[t]; ~i; i = ne[i]){
int j = e[i];
if(dist[j] > dist[t] + w[i]){
dist[j] = dist[t] + w[i];
cnt[j] = cnt[t] + 1; //从t到j多了一条边w[t][j]
if(cnt[j] >= n) return true; //如果这个路径上的边的数量大于n,那说明存在负环,农夫一定可以回到起点
if(!st[j]){
q.push(j);
st[j] = true;
}
}
}
}
return false; //如果一直没有找到负环,说明农夫回不到起点,返回false
}
int main()
{
cin>>T;
while(T -- ){
cin>>n>>m1>>m2;
memset(h, -1, sizeof h);
idx = 0; //记住初始化
for(int i = 0; i < m1; i ++ ){
int a, b, c;
cin>>a>>b>>c;
//正常路径,相当于双向变
add(a, b, c);
add(b, a, c);
}
for(int i = 0; i < m2; i ++ ){
int a, b, c;
cin>>a>>b>>c;
add(a, b, -c); //虫洞相当于一条负权边
}
if(spfa()) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
边栏推荐
猜你喜欢
Make Jar, Not War
从底层结构开始学习FPGA----FIFO IP的定制与测试
Installation of gazebo & connection with ROS
Wood extraction in Halcon
力扣1037. 有效的回旋镖
Let's see through the network i/o model from beginning to end
[advanced C language] 8 written questions of pointer
1123. The nearest common ancestor of the deepest leaf node
微信公众号发送模板消息
[100 cases of JVM tuning practice] 05 - Method area tuning practice (Part 2)
随机推荐
C语言实例_3
Make Jar, Not War
Your cache folder contains root-owned files, due to a bug in npm ERR! previous versions of npm which
Metauniverse urban legend 02: metaphor of the number one player
Neon Optimization: an optimization case of log10 function
域分析工具BloodHound的使用说明
【芯片方案设计】脉搏血氧仪
LeetCode:1175. Prime permutation
Analysis of mutex principle in golang
Oracle: Practice of CDB restricting PDB resources
uva 1401 dp+Trie
The MySQL database in Alibaba cloud was attacked, and finally the data was found
[signal and system]
Yunna | work order management software, work order management software app
LLDP兼容CDP功能配置
AI automatically generates annotation documents from code
编译命令行终端 swift
图片打水印 缩放 和一个输入流的转换
Amway wave C2 tools
C# 计算农历日期方法 2022