Arbitrage POJ - 2240
2024-10-19 17:44:46
题目链接:https://vjudge.net/problem/POJ-2240
思路:判正环,Bellman-ford和SPFA,floyd都可以,有正环就可以套利。
这里用SPFA,就是个板子题吧,把松弛改成乘法操作就好了。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
#include <string>
#include <map>
#include <cmath>
#include <iomanip>
using namespace std; typedef long long LL;
#define inf (1LL << 25)
#define rep(i,j,k) for(int i = (j); i <= (k); i++)
#define rep__(i,j,k) for(int i = (j); i < (k); i++)
#define per(i,j,k) for(int i = (j); i >= (k); i--)
#define per__(i,j,k) for(int i = (j); i > (k); i--) const int N = ;
map<string,int > si; //编号,方便建图
int head[N];
bool vis[N];
int tot[N];
double value[N];
int cnt;
int n; struct Edge{
int to;
double w;
int next;
}e[]; void add(int u,int v,double w){
e[cnt].to = v;
e[cnt].w = w;
e[cnt].next = head[u];
head[u] = cnt++;
} bool SPFA(){ rep(i,,n) value[i] = ;
value[] = ; //随意选个点就行
rep(i,,n) vis[i] = false;
rep(i,,n) tot[i] = ;
vis[] = true;
queue<int> que;
que.push(); while(!que.empty()){
int u = que.front();
que.pop();
vis[u] = false; for(int o = head[u]; ~o; o = e[o].next){
int v = e[o].to;
double w = e[o].w; if(value[v] < value[u] * w){
value[v] = value[u] * w;
if(!vis[v]){
vis[v] = true;
que.push(v);
tot[v]++;
if(tot[v] > n - ) return true; //有正环
}
}
}
} return false; } int main(){ ios::sync_with_stdio(false);
cin.tie(); int tot = ;
while(cin >> n && n){ rep(i,,n) head[i] = -;
cnt = ;
si.clear();
string in;
rep(i,,n){
cin >> in;
si[in] = i;
} int m;
string u,v;
double w; cin >> m;
rep(i,,m){
cin >> u >> w >> v;
add(si[u],si[v],w);
}
cout << "Case " << ++tot << ": ";
if(SPFA()) cout << "Yes" << endl;
else cout << "No" << endl;
} getchar(); getchar();
return ;
}
最新文章
- Linux sudo 命令的应用
- Spring MVC 框架的架包分析,功能作用,优点
- 我的面板我做主 -- 淘宝UWP中自定义Panel的实现
- 协同过滤和简单SVD优化
- IOC框架整体介绍
- Android 各层调用的方式
- mvvm结构中数据的关联----wpf
- active-mq的使用
- JAVA_SE复习(basic)
- POJ 1995 Raising Modulo Numbers
- 解决 Windows instance 时间不同步问题 - 每天5分钟玩转 OpenStack(153)
- 每天一个JS 小demo之树菜单。主要知识点:DOM方法综合运用,递归运用
- COGS 1299. bplusa【听说比a+b还要水的大水题???】
- PHP多个一维数组合并成二维数组的简易方法
- legend2---项目总结(legend2的意义)
- P2158 [SDOI2008] 仪仗队(欧拉函数模板)
- Eonasdan bootstrap datetimepicker 使用记录
- 用.NET WebService Studio调试Web Service解决SOAPAction的问题
- 结构体指针之 段错误 具体解释(segmentation fault)
- docker build 指定dockerfile