poj1860http://poj.org/problem?id=1860
注意:
1、所开数组e的大小
2、bellman算法不再能松弛时结束
3、v[e[j].end]-(v[e[j].start]-e[j].c)*e[j].r<-ADJUST,ADJUST用负号
4、数据类型不要搞错
#include <iostream> #include <fstream> #define ADJUST 0.00000001 using namespace std; struct E { int start; int end; double r; double c; }e[108*108*2]; double v[108]; int m,n,s; double origin; void solved() { int j; origin=v[s]; bool flag; while(v[s]-origin<=ADJUST) { flag=false; for(j=1;j<=m*2;j++) { if(v[e[j].end]-(v[e[j].start]-e[j].c)*e[j].r<-ADJUST) { v[e[j].end]=(v[e[j].start]-e[j].c)*e[j].r; flag=true; } } if(!flag) { if(v[s]-origin>ADJUST) { cout<<"YES"<<endl; return; } else { cout<<"NO"<<endl; return; } } } cout<<"YES"<<endl; } int main() { //ifstream cin("1.txt"); int i,j; for(i=0;i<108;i++) v[i]=0.0; cin>>n>>m>>s; cin>>v[s]; for(i=0,j=1;i<m;i++,j+=2) { int a,b; double rab,rba,cab,cba; cin>>a>>b>>rab>>cab>>rba>>cba; e[j].start=a; e[j].end=b; e[j].r=rab; e[j].c=cab; e[j+1].start=b; e[j+1].end=a; e[j+1].r=rba; e[j+1].c=cba; } solved(); return 0; }
注意:
1、所开数组e的大小
2、bellman算法不再能松弛时结束
3、v[e[j].end]-(v[e[j].start]-e[j].c)*e[j].r<-ADJUST,ADJUST用负号
4、数据类型不要搞错
发表评论
-
2011清华考研机试题2
2011-08-09 14:56 908http://ac.jobdu.com/problem.php ... -
2011清华考研机试题1
2011-08-09 14:40 642题目描述 http://ac.jobdu.com/proble ... -
考研清华2011复试机考第三题
2011-08-09 13:51 1491题目描述 在某条线路上有N个火车站,有三种距离的路程,L1, ... -
poj3259 spfa解法
2011-08-08 19:59 1356同上题,不过改的spfa算法,注意每个节点进入队列的次数至多为 ... -
poj3259 bellman水题
2011-08-08 17:04 969poj3259http://poj.org/problem?i ... -
acm题目常用的预处理
2011-08-08 15:26 1163#include<iostream> #in ... -
water~9
2011-08-06 18:01 418poj2109http://poj.org/problem?i ... -
water~8
2011-08-06 17:22 574poj2027http://poj.org/problem?i ... -
water~7
2011-08-06 17:15 567poj1328http://poj.org/problem?i ... -
water~6
2011-08-06 14:27 707poj1088http://poj.org/problem?i ... -
water~5
2011-08-06 14:24 581poj1003http://poj.org/problem?i ... -
water~4
2011-08-06 14:09 637poj1004http://poj.org/problem?i ... -
water~3
2011-08-06 13:59 522poj2159http://poj.org/problem?i ... -
water~2
2011-08-06 12:10 533poj3299http://poj.org/problem?i ... -
water~1
2011-08-06 10:35 639poj1503http://poj.org/problem?i ... -
POJ3280 简单DP
2011-08-05 14:48 893poj3280:http://poj.org/problem? ... -
POJ3253
2011-08-04 13:36 780poj3253:http://poj.org/problem? ...
相关推荐
北大POJ1860-Currency Exchange【Bellman】 解题报告+AC代码
(poj1860,poj3259,poj1062,poj2253,poj1125,poj2240) (3)最小生成树算法(prim,kruskal) (poj1789,poj2485,poj1258,poj3026) (4)拓扑排序 (poj1094) (5)二分图的最大匹配 (匈牙利算法) (poj3041,poj3020) ...
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
北大POJ1159-Palindrome 解题报告+AC代码
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
poj分类poj分类poj分类poj分类
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
北大POJ2002-Squares 解题报告+AC代码
POJ1048,加强版的约瑟夫问题 难度中等
POJ1083的代码,POJ1083的代码,POJ1083的代码
poj 百练 题目分类 poj 百练 题目分类
poj 1001答案
POJ上的一道题目,自己写的代码,因为想下载别人的, 所以就放上了。
POJ2968代码有用,欢迎下载,POJ代码