题目地址：http://poj.org/problem?id=1860
正好是Bellman的逆运算
求的是最长路径，且如果有一条能一直走的正环(代表资产一直增加)就输出YES
#include<iostream> #include<cstdio> #include<vector> #include<algorithm> using namespace std; const int INF=(1<<30); struct Edge{ int from,to; double r,c; Edge(int f,int t,double r,double c):from(f),to(t),r(r),c(c){} }; vector<Edge> edges; double d[100+5]; bool Bellman_ford(int s,double val,int n) { fill(d+1,d+n+1,0); d[s]=val; for(int k=1;k<n;k++) //从u~v点经过k条边 for(int i=0;i<edges.size();i++) { int u=edges[i].from; int v=edges[i].to; double r=edges[i].r, c=edges[i].c; if(d[v]<(d[u]-c)*r) d[v]=(d[u]-c)*r; } for(int i=0;i<edges.size();i++){ int u=edges[i].from; int v=edges[i].to; double r=edges[i].r, c=edges[i].c; if(d[v]<(d[u]-c)*r) return true; } return false; } int main() { int n,m,s; double val; cin>>n>>m>>s>>val; int u,v; double r,c; for(int i=0;i<m;i++) { cin>>u>>v>>r>>c; edges.push_back(Edge(u,v,r,c)); cin>>r>>c; edges.push_back(Edge(v,u,r,c)); } cout<<(Bellman_ford(s,val,n)?"YES":"NO")<<endl; return 0; }