栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 面试经验 > 面试问答

poj 3860 Fruit Weights

面试问答 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

poj 3860 Fruit Weights

#include <cstdio>#include <cstring>#include <map>#include <string>#include <iostream>#include <algorithm>using namespace std;typedef long long LL;const int MAXN = 220;const double EPS = 1e-8;map<string, int> mp;string a, b;int m, n;double x, y;int aid, bid;double mat[MAXN][MAXN];inline int sgn(double x) {    return (x > EPS) - (x < -EPS);}bool floyd() {    for(int k = 1; k <= n; ++k)        for(int i = 1; i <= n; ++i) if(mat[i][k] > 0) for(int j = 1; j <= n; ++j) if(mat[k][j] > 0)     if(mat[i][j] < 0 || mat[i][k] * mat[k][j] < mat[i][j]) mat[i][j] = mat[i][k] * mat[k][j];    for(int i = 1; i <= n; ++i)        for(int j = i + 1; j <= n; ++j) { if(mat[i][j] < 0 || mat[j][i] < 0) continue; if(sgn(mat[i][j] * mat[j][i] - 1) < 0) return false;        }    return true;}int main() {    ios::sync_with_stdio(false);    while(cin>>m) {        if(m == 0) break;        n = 0;        mp.clear();        for(int i = 1; i < MAXN; ++i) { for(int j = 1; j < MAXN; ++j) mat[i][j] = -1; mat[i][i] = 1;        }        for(int i = 0; i < m; ++i) { cin>>x>>a>>y>>b; if(mp.find(a) != mp.end()) aid = mp[a]; else mp[a] = aid = ++n; if(mp.find(b) != mp.end()) bid = mp[b]; else mp[b] = bid = ++n; if(aid == bid) continue; //if(mat[aid][bid] < double(x, y)) mat[aid][bid] = double(x, y); if(mat[bid][aid] < 0 || mat[bid][aid] > y / x) mat[bid][aid] = y / x;        }        cin>>x>>a>>y>>b;        if(!floyd()) { puts("INCONSISTENT"); continue;        }        if(mp.find(a) == mp.end() || mp.find(b) == mp.end()) { puts("UNAVAILABLE"); continue;        }        aid = mp[a];        bid = mp[b];        if(sgn(mat[aid][bid] - x / y) == 0  && sgn(mat[bid][aid] - y / x) == 0) { puts("=="); continue;        }        if(mat[bid][aid] > 0 && sgn(mat[bid][aid] - y / x) <= 0) { puts("<="); continue;        }        if(mat[aid][bid] > 0 && sgn(mat[aid][bid] - x / y) <= 0) { puts(">="); continue;        }        puts("UNAVAILABLE");    }}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/366600.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号