【POJ 1860】 Currency Exchange
模拟货比交易 输入数据n 货币种类 m 交易种类 s 初始货币类型 v 初始持币数 m行分别为 A B(该种交易的两种货币A、B) RAB, CAB, RBA ,CBA A->B和B->A的交易汇率和手续费 交易后金额为(s-c)*r 最短路模板题 遍历看是否有正环(即可无限增加资本)
写了两种做法 SPFA比BellMan耗时长 可啪
SPFA
;typedef struct Edge{int v;double r,c;}Edge;Edge eg;double dis[111];int in[111];bool vis[111];vector <Edge> vct[111];int n,m,s;int dcmp(double x){return x < -esp? -1: x > esp;}bool SPFA(double st){memset(dis,0,sizeof(dis));memset(in,0,sizeof(in));dis[s] = st;queue <int> q;q.push(s);int i,x,u,v;double c,r;while(!q.empty()){u = q.front();q.pop();vis[u] = 0;for(i = 0; i < vct[u].size(); ++i){v = vct[u][i].v;c = vct[u][i].c;r = vct[u][i].r;if(dcmp(dis[v] – (dis[u]-c)*r) < 0){dis[v] = (dis[u]-c)*r;if(!vis[v]){in[v]++;if(in[v] > n) return true;q.push(v);vis[v] = 1;}}}}return false;}int main(){int i,u,v;double sum;scanf(“%d %d %d %lf”,&n,&m,&s,&sum);for(i = 0; i < m; ++i){scanf(“%d %d %lf %lf”,&u,&v,&eg.r,&eg.c);eg.v = v;vct[u].push_back(eg);scanf(“%lf %lf”,&eg.r,&eg.c);eg.v = u;vct[v].push_back(eg);}if(SPFA(sum)) printf(“YES\n”);else printf(“NO\n”);return 0;}
BellMan-Ford
;typedef struct Edge{int u,v;double r,c;}Edge;Edge eg;double dis[111];vector <Edge> vct;int n,m,s;int dcmp(double x){return x < -esp? -1: x > esp;}bool BellMan_Ford(double st){memset(dis,0,sizeof(dis));dis[s] = st;int i,j,k,u,v,f;double r,c;for(i = 1; i < n; ++i){f = 0;for(j = 0; j < vct.size(); ++j){u = vct[j].u;v = vct[j].v;r = vct[j].r;c = vct[j].c;if(dcmp(dis[v] – (dis[u]-c)*r) < 0){dis[v] = (dis[u]-c)*r;f = 1;}}if(!f) return false;}for(j = 0; j < vct.size(); ++j){u = vct[j].u;v = vct[j].v;r = vct[j].r;c = vct[j].c;if(dcmp(dis[v] – (dis[u]-c)*r) < 0){return true;}}return false;}int main(){int i,u,v;double sum;scanf(“%d %d %d %lf”,&n,&m,&s,&sum);for(i = 0; i < m; ++i){scanf(“%d %d %lf %lf”,&u,&v,&eg.r,&eg.c);eg.v = v;eg.u = u;vct.push_back(eg);scanf(“%lf %lf”,&eg.r,&eg.c);eg.v = u;eg.u = v;vct.push_back(eg);}if(BellMan_Ford(sum)) printf(“YES\n”);else printf(“NO\n”);return 0;}
，别人失去了信心，他却下决心实现自己的目标。
