网站描述更改,whois查询,中国核工业华兴建设有限公司,网络维修1 /**2 problem: http://poj.org/problem?id32593 spfa判负环#xff1a;4 当有个点被松弛了n次#xff0c;则这个点必定为负环中的一个点#xff08;n为点的个数#xff09;5 spfa双端队列优化#xff1a;6 维护队列使其dist小的点优先处理7 **/8 #includestdio.h32593 spfa判负环4 当有个点被松弛了n次则这个点必定为负环中的一个点n为点的个数5 spfa双端队列优化6 维护队列使其dist小的点优先处理7 **/8 #includestdio.h9 #includedeque
10 #includealgorithm
11 using namespace std;
12
13 class Graphics{
14 const static int MAXN 505;
15 const static int MAXM 2505 * 2 205;
16 const static int INF 0x7fffffff;
17 private:
18 struct Edge{
19 int to, dist, next;
20 }edge[MAXM];
21 int first[MAXN], sign, sumOfPoint;
22 public:
23 void init(int n){
24 sumOfPoint n;
25 for(int i 1; i n; i ){
26 first[i] -1;
27 }
28 sign 0;
29 }
30 void addEdgeOneWay(int u, int v, int w){
31 edge[sign].dist w;
32 edge[sign].to v;
33 edge[sign].next first[u];
34 first[u] sign ;
35 }
36 void addEdgeTwoWay(int u, int v, int w){
37 addEdgeOneWay(u, v, w);
38 addEdgeOneWay(v, u, w);
39 }
40 bool spfaNegRing(int start){
41 bool *vis new bool[sumOfPoint1];
42 int *dist new int[sumOfPoint1];
43 int *cnt new int[sumOfPoint1];
44 for(int i 1; i sumOfPoint; i ){
45 vis[i] 0;
46 cnt[i] 0;
47 dist[i] INF;
48 }
49 dequeint que;
50 que.push_front(start);
51 dist[start] 0;
52 vis[start] 1;
53 while(!que.empty()){
54 int now que.front();
55 que.pop_front();
56 vis[now] 0;
57 for(int i first[now]; i ! -1; i edge[i].next){
58 int to edge[i].to, eDist edge[i].dist;
59 if(dist[now] eDist dist[to]){
60 dist[to] dist[now] eDist;
61 cnt[to] ;
62 if(cnt[to] sumOfPoint) { /// 如果这个点已经松弛n次则它必定是负环中的一个点
63 delete []vis; delete []dist; return true;
64 }
65 if(!vis[to]){
66 vis[to] 1;
67 if(que.empty() || dist[to] dist[que.front()])
68 que.push_front(to);
69 else
70 que.push_back(to);
71 }
72 }
73 }
74 }
75 delete []vis; delete []dist; return false;
76 }
77 }graph;
78
79 int main(){
80 int f;
81 scanf(%d, f);
82 while(f --){
83 int n, m, w;
84 scanf(%d%d%d, n, m, w);
85 graph.init(n);
86 while(m --){
87 int s, e, t;
88 scanf(%d%d%d, s, e, t);
89 graph.addEdgeTwoWay(s, e, t);
90 }
91 while(w --){
92 int s, e, t;
93 scanf(%d%d%d, s, e, t);
94 graph.addEdgeOneWay(s, e, -t);
95 }
96 printf(%s\n, graph.spfaNegRing(1) ? YES : NO);
97 }
98 return 0;
99 } 转载于:https://www.cnblogs.com/DarkScoCu/p/10527359.html
