[最短路]JZOJ 3241 Money

ゝ一纸荒年。 2021-12-16 01:09 128阅读 0赞

#### Description ####

你在一个跨国公司负责发工资，每个工人的工资以自己本国货币结算。如果你手头上有足够的该国货币，你就直接发给他；如果没有足够的该国货币，他也不介意收到其他种类的货币，前提是按兑换关系他没有少拿就可以了。例如，有六种货币：A,B,C,D,E,F，你知道这些货币的兑换关系是：  
  
23 A = 17 B  
  
16 C = 29 E  
  
5 B = 14 E  
  
1 D = 7 F  
  
假如有个工人过来领100 A，而你手头正好没这么多A货币，你可以考虑替换成74 B（相当于100.12 A）、115 C（相当于100.72 A）或207 E（相当于100.02 A）。你应该支付207 E，因为这最接近这个工人应得的工资。  
  
注意根据以上的兑换关系，你无法推断货币A与D、A与F的兑换关系。  
  
由于钱仓空间有限，每种货币你最多只能持有100000，因此你无法用E货币支付64000 A，但用73078 C来支付是允许的。  
  
假设工人领工资时，你正好没有结算的货币了，但其他货币的钱仓都是满的。你需要写一个程序帮你计算该怎样支付这个工人的工资。

#### Input ####

输入的第一行是一个整数n，接下来的n行，每行有两种不同货币的兑换关系，形如：  
  
val1 name1 = val2 name2  
  
name1和name2分别是货币名，val 1和val 2是<=30的正整数，货币种类不超过8个，货币名由不超过10个字母组成。  
  
兑换关系不存在类似1 A = 2B，1B = 2C，1C = 2A这种矛盾的情况。  
  
紧接着有一行形如val name，代表工资额和结算的货币（val不超过100000）。

#### Output ####

输出形式为val name，val和name之间用一个空格分隔，分别代表支付的工资额及相应的货币。每个测试数据保证有唯一解。

#### Sample Input ####

输入1：
    
    4
    
    23 A = 17 B
    
    16 C = 29 E
    
    5 B = 14 E
    
    1 D = 7 F
    
    100 A
    
    
    输入2：
    
    1
    
    1 USD = 2 RMB
    
    40 RMB

#### Sample Output ####

输出1：
    
    207 E
    
    
    输出2：
    
    20 USD

#### Data Constraint ####

货币种类不超过8个

# 分析 #

其实根本不需要最短路……货币关系不能矛盾，就好像你用RMB换日元再换成美刀和直接换成美刀一样，钱数不变……

然后一波乱搞，为了防止精度出问题，我整个运算过程用的是结构体，用分子分母表示

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <memory.h>
    #include <queue>
    #include <cmath>
    using namespace std;
    typedef long long ll;
    const int N=9;
    const ll Inf=1e5+1;
    struct Float {
        ll z,m;
        friend bool operator < (Float a,Float b) {
            return a.z*b.m<a.m*b.z;
        }
        friend Float operator * (Float a,Float b) {
            return (Float){a.z*b.z,a.m*b.m};
        }
    };
    struct Graph {
        int v,nx;
        Float f;
    }g[2*N*N];
    int cnt,list[N];
    Float dis[N],mx=(Float){
         1,Inf};
    int end;
    bool vis[N];
    string a[N],c;
    int acnt;
    int n,need,kind;
    
    void Add(int u,int v,int z,int m) {
        g[++cnt]=(Graph){v,list[u],(Float){m,z}};list[u]=cnt;
        g[++cnt]=(Graph){u,list[v],(Float){z,m}};list[v]=cnt;
    }
    
    bool Check(Float a) {
        ll b=1.0*a.z/a.m+(a.z%a.m?1:0);
        return b<Inf;
    }
    
    void SPFA() {
         queue<int> q;
        while (!q.empty()) q.pop();
        memset(vis,0,sizeof vis);
        for (int i=1;i<=acnt;i++) dis[i]=(Float){
         1,Inf};
        q.push(kind);dis[kind]=(Float){need,1};vis[kind]=1;
        while (!q.empty()) {
            int u=q.front();q.pop();
            for (int i=list[u];i;i=g[i].nx)
                if (dis[g[i].v]<dis[u]*g[i].f) {
                    dis[g[i].v]=dis[u]*g[i].f;
                    if (!vis[g[i].v]) q.push(g[i].v);
                    vis[g[i].v]=1;
                }
            vis[u]=0;
        }
    }
    
    int main() {
        scanf("%d",&n);
        for (int i=1;i<=n;i++) {
            int z,m,u=0,v=0;
            scanf("%d ",&z);
            cin>>c;
            cin>>a[0];
            for (int j=1;j<=acnt;j++)
                if (c==a[j]) {
                    u=j;
                    break;
                }
            if (!u) u=++acnt,a[acnt]=c;
            scanf("%d ",&m);
            cin>>c;
            for (int j=1;j<=acnt;j++)
                if (c==a[j]) {
                    v=j;
                    break;
                }
            if (!v) v=++acnt,a[acnt]=c;
            Add(u,v,z,m);
        }
        scanf("%d ",&need);
        cin>>c;
        for (int i=1;i<=acnt;i++)
            if (c==a[i]) {
                kind=i;
                break;
            }
        SPFA();
        for (int i=1;i<=acnt;i++)
            if (Check(dis[i])&&1.0*(1ll*dis[i].z/dis[i].m+(dis[i].z%dis[i].m?1:0))*dis[i].m/dis[i].z<1.0*(1ll*mx.z/mx.m+(mx.z%mx.m?1:0))*mx.m/mx.z&&i!=kind) {
                mx=dis[i];
                end=i;
            }
        printf("%lld ",(ll)(1.0*mx.z/mx.m+(mx.z%mx.m?1:0)));
        cout<<a[end];
        return 0;
    }

转载于:https://www.cnblogs.com/mastervan/p/11117923.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211215/356479831f0343a7bf934f711833f2ec.png