这题类似于Bellman－Ford，但是不是求负权环，而是求正权环。
// // main.cpp // Richard // // Created by 邵金杰 on 16/8/12. // Copyright © 2016年 邵金杰. All rights reserved. // #include<cstdio> #include<vector> #include<cstring> using namespace std; const int maxn=100+10; struct edge{ int s,e; double r,c; edge(int s,int e,double r,double c): s(s),e(e),r(r),c(c) {} }; vector<edge> edges; double dist[maxn]; bool Bellman_Ford(int n,int S,double V) { memset(dist,0,sizeof(dist)); dist[S]=V; for(int k=1;k<n;k++) { for(int i=0;i<edges.size();i++) { int s=edges[i].s; int e=edges[i].e; if((dist[s]-edges[i].c)*edges[i].r>dist[e]) dist[e]=(dist[s]-edges[i].c)*edges[i].r; } } for(int i=0;i<edges.size();i++) { int s=edges[i].s; int e=edges[i].e; if((dist[s]-edges[i].c)*edges[i].r>dist[e]) return true; } return false; } int main() { int N,M,S; double V; scanf("%d%d%d%lf",&N,&M,&S,&V); int s,e; double r1,c1,r2,c2; for(int i=0;i<M;i++) { scanf("%d%d%lf%lf%lf%lf",&s,&e,&r1,&c1,&r2,&c2); edges.push_back(edge(s,e,r1,c1)); edges.push_back(edge(e,s,r2,c2)); } if(Bellman_Ford(N,S,V)) printf("YES\n"); else printf("NO\n"); }