首页 技术 正文
技术 2022年11月23日
0 收藏 371 点赞 2,695 浏览 1176 个字

http://poj.org/problem?id=2240

用log化乘法为加法找正圈

c++ 110ms,g++tle

#include <string>
#include <map>
#include <iostream>
#include <cmath>
#include <cstring>
#include <queue>
using namespace std;
const int maxn = 50;
bool vis[maxn];
double chg[maxn][maxn];
double dis[maxn];
int e[maxn][maxn],deg[maxn];
map<string,int> idmp;
int n,m;
const double inf = 0x3fffffff;queue<int> que;
bool hasloop(int s){
while(!que.empty())que.pop();
que.push(s);
vis[s] = true;
int cnt = 0;
while(!que.empty()){
cnt ++;
s = que.front();que.pop();vis[s] = false;
for(int i = 0;i < deg[s];i++)
{
int t = e[s][i];
if(dis[t] < dis[s] + chg[s][t])
{
dis[t] = dis[s] + chg[s][t];
que.push(t);
vis[t] = true;
}
}
if(cnt > n * n)return true;
}
return false;
}int main(){
int ti = 0;
while(cin>>n && n && ++ti){
idmp.clear();
for(int i = 0;i < n;i++)
{
dis[i] = -inf;
for(int j = 0;j < n;j++)chg[i][j] = -inf;
}
memset(vis,false,sizeof vis);
memset(deg,0,sizeof deg); for(int i = 0;i < n;i++)
{
string tmp;
cin>>tmp;
idmp[tmp] = i;
}
cin>>m;
for(int i = 0;i < m;i++)
{
string sf,st;
double change;
cin>>sf>>change>>st;
change = log(change);
int f = idmp[sf];
int t = idmp[st];
chg[f][t] = change;
e[f][deg[f]++] = t;
}
bool fl = false;
for(int i = 0;i < n;i++)
{
if(dis[i] == -inf){
dis[i] = 1;
if(hasloop(i)){
fl = true;
break;
}
}
}
cout << "Case " << ti << ": ";
if(fl)cout << "Yes" <<endl;
else cout << "No" << endl;
}
return 0;
}

  

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141236.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:877 阅读:6,217
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:806 阅读:4,049
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:566 阅读:4,851
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:732 阅读:4,786
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:5,874
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,567
助力内容变现

将您的收入提升到一个新的水平

点击联系客服

在线时间:8:00-16:00

客服电话

400-888-8888

客服邮箱

ceotheme@ceo.com

扫描二维码

关注微信公众号

扫描二维码

手机访问本站