Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
代码:纪念第一次真正用bellman//poj 1860 #include <iostream> using namespace std; int E[202][2];//记录坐标 double EE[202][2],V[101];//M*2条边,EE[][0]记录汇率,EE[][1]记录手续费 int n,m,s,x,y; double v; int find_negative_loop(){ V[s]=v; for(int i=1;i<=n;i++){//最多只有n种money 树的高度不可能大于n-1,否则形成负圈 bool update=false;//如果该层树不需要再添加了,直接退出以节约时间 for(int j=0;j<2*m;j++){//有来回,一组数据提供两条边,2*m-1,wa一回 if((V[E[j][0]]-EE[j][1])*EE[j][0]>V[E[j][1]]){//如果这条边满足条件可以被添加进树 V[E[j][1]]=(V[E[j][0]]-EE[j][1])*EE[j][0];//树的高度隐含增加 update=true; if(i==n)return 1;//如果树的高度为n,则首尾相连,此时'负'圈可能已经循环过几圈了 } } if(!update)break; } return 0; } int main(){ cin>>n>>m>>s>>v;//n money 种类 m 站点数 int t,i; for(i=t=0;i<m;i++){ cin>>x>>y>>EE[t][0]>>EE[t][1]>>EE[t+1][0]>>EE[t+1][1]; t++; E[t-1][0]=x; E[t-1][1]=y; E[t][0]=y; E[t][1]=x; t++; } if(find_negative_loop()){ cout<<"YES"<<endl; } else cout<<"NO"<<endl; return 0; } //poj 1860 #include <iostream> #include <queue> using namespace std; int E[202][2]; double EE[202][2],V[101];//M*2条边 int num[202];//用于统计入队次数 int n,m,s,x,y; double v; queue <int> que; int temp; double tt; int find_negative_loop(){ while(!que.empty()){ temp=que.front(); tt=V[E[temp][0]]; que.pop(); if(V[E[temp][1]]<(V[E[temp][0]]-EE[temp][1])*EE[temp][0]){ V[E[temp][1]]=(V[E[temp][0]]-EE[temp][1])*EE[temp][0]; for(int i=0;i<2*m;i++){ if(E[temp][1]==E[i][0]){ num[i]++; if(num[i]==n)return 1; que.push(i); } } } } return 0; } int main(){ cin>>n>>m>>s>>v;//n money 种类 m 站点数 int t,i; num[0]++; V[s]=v; for(i=t=0;i<m;i++){ cin>>x>>y>>EE[t][0]>>EE[t][1]>>EE[t+1][0]>>EE[t+1][1]; que.push(t); t++; E[t-1][0]=x; E[t-1][1]=y; E[t][0]=y; E[t][1]=x; que.push(t); t++; } if(find_negative_loop()){ cout<<"YES"<<endl; } else cout<<"NO"<<endl; return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator