UVALive 4431 Fruit Weights --floyd,差分约束?

时间:2023-03-09 22:36:55
UVALive 4431 Fruit Weights --floyd,差分约束?

题意: 给出一些关系用aX <= bY表示, 最后查询aX 和 bY的关系,是>=,==,<=,还是不能确定,还是出现了矛盾。

解法:对每一个关系其实都可以建一条X->Y的边,边权为b/a,表示X <= b/a*Y,输入完后,跑一遍floyd,对每一对点A,B跑出A<=xB的x的最小值。

因为如果真的存b/a的话,可能会损失很大的精度,但是好像这样也能过。为了更加保险,我们可以取个对数,log(b/a) = log(b)-log(a),那么乘法就变成了加法,更好计算,也更加准确。

最后就是判断了,设最后查询的是k1,k2两个点,比率为ka,kb

1.==: 如果mp[k1][k2] == -mp[k2][k1], 即是倒数关系(对数是负数关系),且mp[k1][k2] = log(kb/ka),那么就相等。

2.<=: 如果mp[k1][k2] <= log(kb/ka), 现在k1已经小于等于mp[k1][k2]了,那么肯定是小于等于log(kb/ka)的。

3.>=: -mp[k2][k1] >= log(kb/ka)

4.INCONSISTENT: 如果某个mp[i][i]为负,说明有矛盾。

5.其他情况

代码:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#define Mod 1000000007
#define eps 1e-8
using namespace std; double mp[][];
map<string,int> ms; int sgn(double x) {
if(x > eps) return ;
if(x < -eps) return -;
return ;
} int main()
{
int n,i,j,a,b,tot,u,v,k;
string S;
while(scanf("%d",&n)!=EOF && n)
{
tot = ;
ms.clear();
for(i=;i<=*n;i++) {
for(j=;j<=*n;j++)
mp[i][j] = Mod;
mp[i][i] = 0.0;
}
for(i=;i<=n;i++) {
scanf("%d",&a);
cin>>S;
if(!ms[S]) ms[S] = ++tot;
u = ms[S];
scanf("%d",&b);
cin>>S;
if(!ms[S]) ms[S] = ++tot;
v = ms[S];
mp[u][v] = min(mp[u][v],log((double)b/(double)a));
}
for(k=;k<=tot;k++) {
for(i=;i<=tot;i++) {
for(j=;j<=tot;j++)
mp[i][j] = min(mp[i][j],mp[i][k]+mp[k][j]);
}
}
string S1,S2;
scanf("%d",&a);
cin>>S1;
int k1 = ms[S1];
scanf("%d",&b);
cin>>S2;
int k2 = ms[S2];
double rate = log((double)b/(double)a);
if(ms[S1] == || ms[S2] == ) { puts("UNAVAILABLE"); continue; }
for(i=;i<=tot;i++) if(sgn(mp[i][i]) < ) { puts("INCONSISTENT"); break; }
if(i != tot+) continue;
if(sgn(mp[k1][k2]+mp[k2][k1]) == && sgn(mp[k1][k2]-rate) == ) puts("==");
else if(sgn(mp[k1][k2]-rate) <= ) puts("<=");
else if(sgn(-mp[k2][k1]-rate) >= ) puts(">=");
else puts("UNAVAILABLE");
}
return ;
}