题目链接: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 ;
}

最新文章

  1. Linux sudo 命令的应用
  2. Spring MVC 框架的架包分析,功能作用,优点
  3. 我的面板我做主 -- 淘宝UWP中自定义Panel的实现
  4. 协同过滤和简单SVD优化
  5. IOC框架整体介绍
  6. Android 各层调用的方式
  7. mvvm结构中数据的关联----wpf
  8. active-mq的使用
  9. JAVA_SE复习(basic)
  10. POJ 1995 Raising Modulo Numbers
  11. 解决 Windows instance 时间不同步问题 - 每天5分钟玩转 OpenStack(153)
  12. 每天一个JS 小demo之树菜单。主要知识点:DOM方法综合运用,递归运用
  13. COGS 1299. bplusa【听说比a+b还要水的大水题???】
  14. PHP多个一维数组合并成二维数组的简易方法
  15. legend2---项目总结(legend2的意义)
  16. P2158 [SDOI2008] 仪仗队(欧拉函数模板)
  17. Eonasdan bootstrap datetimepicker 使用记录
  18. 用.NET WebService Studio调试Web Service解决SOAPAction的问题
  19. 结构体指针之 段错误 具体解释(segmentation fault)
  20. docker build 指定dockerfile

热门文章

  1. Apache(基于端口号)
  2. 20191004 「HZOJ NOIP2019 Round #9」20191004模拟
  3. 【BZOJ3171】[TJOI2013] 循环格(网络流)
  4. ubuntu 查看版本
  5. 纯CSS打造BiliBili样式博客主题
  6. centos7彻底卸载mysql和通过yum安装mysql
  7. client-go客户端自定义开发Kubernetes及源码分析
  8. MySQL 合并字段及列转行
  9. Oracle 原生驱动带来的精度问题的分析与解决
  10. dubbo入门学习