当前位置:网站首页>AcWing 904. Wormhole solution (SPFA for negative rings)
AcWing 904. Wormhole solution (SPFA for negative rings)
2022-07-07 01:36:00 【Mr. Qiao Da】
AcWing 904. Wormhole
A negative ring is a ring in which the sum of the weights in the graph is negative , If there is a negative ring in the graph , Then the farmer must be able to return to the starting point , On the contrary, it must not , So this is a naked problem of finding negative rings . use spfa Record the number of edges on the shortest path , If the number of edges on a path is greater than or equal to n, Then it can be determined that there is a negative ring on this road , return true that will do , Instead, return to 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]; // Shortest distance record array
int cnt[N]; // Record the number of sides of the shortest distance
void add(int a, int b, int c){
e[idx] = b;
ne[idx] = h[a];
w[idx] = c;
h[a] = idx ++ ;
}
bool spfa(){
// Judge negative loop
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; // from t To j One more side w[t][j]
if(cnt[j] >= n) return true; // If the number of edges on this path is greater than n, That means there is a negative ring , The farmer must be able to return to the starting point
if(!st[j]){
q.push(j);
st[j] = true;
}
}
}
}
return false; // If you haven't found a negative ring , It means that the farmer cannot return to the starting point , return false
}
int main()
{
cin>>T;
while(T -- ){
cin>>n>>m1>>m2;
memset(h, -1, sizeof h);
idx = 0; // Remember to initialize
for(int i = 0; i < m1; i ++ ){
int a, b, c;
cin>>a>>b>>c;
// Normal path , Equivalent to Bidirectional Transformation
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); // Wormhole is equivalent to a negative weight edge
}
if(spfa()) cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
return 0;
}
边栏推荐
- docker 方法安装mysql
- 对C语言数组的再认识
- 2022 Google CTF SEGFAULT LABYRINTH wp
- mongodb查看表是否导入成功
- mysqlbackup 还原特定的表
- Neon Optimization: summary of performance optimization experience
- THREE.AxesHelper is not a constructor
- Share a general compilation method of so dynamic library
- Taro 小程序开启wxml代码压缩
- Taro2.* applet configuration sharing wechat circle of friends
猜你喜欢
Appium foundation - appium inspector positioning tool (I)
Today's question -2022/7/4 modify string reference type variables in lambda body
云呐|工单管理办法,如何开展工单管理
Your cache folder contains root-owned files, due to a bug in npm ERR! previous versions of npm which
修改px4飞控的系统时间
AI 从代码中自动生成注释文档
AcWing 361. 观光奶牛 题解(spfa求正环)
tansig和logsig的差异,为什么BP喜欢用tansig
[advanced C language] 8 written questions of pointer
新工作感悟~辞旧迎新~
随机推荐
Transformation transformation operator
Body mass index program, entry to write dead applet project
编译命令行终端 swift
【信号与系统】
taro3.*中使用 dva 入门级别的哦
454-百度面经1
C language instance_ four
AcWing 1148. 秘密的牛奶运输 题解(最小生成树)
安全保护能力是什么意思?等保不同级别保护能力分别是怎样?
AcWing 1142. 繁忙的都市 题解(最小生成树)
图片打水印 缩放 和一个输入流的转换
THREE.AxesHelper is not a constructor
C语言实例_2
ZOJ Problem Set – 2563 Long Dominoes 【如压力dp】
Spark TPCDS Data Gen
Clickhouse fields are grouped and aggregated, and SQL is queried according to the granularity of any time period
糊涂工具类(hutool)post请求设置body参数为json数据
2022 Google CTF SEGFAULT LABYRINTH wp
dvajs的基础介绍及使用
从底层结构开始学习FPGA----FIFO IP的定制与测试