英語太渣讀了半天，理解了題意就好辦了……Bellman_ford算法。在n-1次松弛后，如果依然存在滿足松弛的情況返回1.說簡單點就是判讀是否存在正環。

#include<stdio.h>
#include<string.h>
#include<cstring>
#include<string>
#include<math.h>
#include<queue>
#include<algorithm>
#include<iostream>
#include<stdlib.h>
#include<cmath>#define INF 0x3f3f3f3f
#define MAX 1000005using namespace std;struct node
{int a,b;double e,c;
}Map[MAX];int n,m,s,k;double dist[MAX],v;int bellman_ford()
{int i,j,ok;memset(dist,0,sizeof(dist));dist[s]=v;for(i=1;i<n;i++){ok=0;for(j=1;j<k;j++){if(dist[Map[j].b] < (dist[Map[j].a] - Map[j].c)*Map[j].e){dist[Map[j].b] = (dist[Map[j].a] - Map[j].c)*Map[j].e;ok=1;}}if(!ok)break;}for(j=1;j<k;j++){if(dist[Map[j].b] < (dist[Map[j].a] - Map[j].c)*Map[j].e)return 1;}return 0;
}int main()
{int i,j,a,b;double e1,c1,e2,c2;while(scanf("%d%d%d%lf",&n,&m,&s,&v)!=EOF){k=1;for(i=1;i<=m;i++){scanf("%d%d%lf%lf%lf%lf",&a,&b,&e1,&c1,&e2,&c2);Map[k].a=a;Map[k].b=b;Map[k].e=e1;Map[k++].c=c1;Map[k].a=b;Map[k].b=a;Map[k].e=e2;Map[k++].c=c2;}int ok=bellman_ford();if(ok)printf("YES\n");elseprintf("NO\n");}return 0;
}

　　

轉載于:https://www.cnblogs.com/alan-W/p/5665260.html

總結

以上是生活随笔為你收集整理的POJ 1860Currency Exchange的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。