寻找正权环就是常规Bellman算法的反向操作,将松弛更小值改为松弛更大值。
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
#include <queue>
#include <string>
#include <map>
#include <stack>
#define MAXN 104
#define MOD 1000000009
#define INF 0x7ffffff
#define lowbit(x) (x)&(-x)
using namespace std;
struct EDGE{
int u;
int v;
double r;
double c;
}edge[204];
int n,m,s;
double v;
double dis[MAXN];
int cnt;
void init(){
for(int i=1;i<=n;++i){
dis[i] = 0.0;
}
dis[s] = v;
cnt = 0;
}
bool Bellman(){
for(int i=1;i<n;++i){
for(int j=0;j<cnt;++j){
int u = edge[j].u;
int v = edge[j].v;
double r = edge[j].r;
double c = edge[j].c;
if(dis[v] < (dis[u]-c)*r){
dis[v] = (dis[u]-c)*r;
}
}
}
for(int i=0;i<cnt;++i){
int u = edge[i].u;
int v = edge[i].v;
double r = edge[i].r;
double c = edge[i].c;
if(dis[v] < (dis[u]-c)*r){
return true;
}
}
return false;
}
inline void add(int u,int v,double r,double c){
edge[cnt].u = u;
edge[cnt].v = v;;
edge[cnt].r = r;
edge[cnt].c = c;
++cnt;
}
int main(){
while(cin >> n >> m >> s >> v){
init();
int a,b;
double r1,c1,r2,c2;
while(m--){
cin >> a >> b;
cin >> r1 >> c1 >> r2 >> c2;
add(a,b,r1,c1);
add(b,a,r2,c2);
}
if(Bellman()) cout << "YES" << endl;
else cout << "NO" << endl;
}
return 0;
}