| ||||||||||
| 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