Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

代码:纪念第一次真正用bellman

Posted by xuesu at 2014-02-25 18:49:40 on Problem 1860 and last updated at 2014-02-27 13:21:37
//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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator