题解：P13141 [GCJ 2018 #1B] Transmutation

ZBH_799 · 2025-08-13 20:01:43 · 题解

题目分析

显然，如果可以造出 x 吨铅，那么 0 \sim x 吨铅肯定都能造出，因此我们考虑二分答案。如何写检查函数呢？我们可以记录两个数组 need,now，表示当前金属的库存和需求。对于需求比库存多的金属，它显然需要用两种合成材料合成出缺少的该金属，则两种材料的需求需要加上当前金属缺少的部分。代码如下：

for(int i=1;i<=n;i++){
    if(ned[i]<=now[i]){
        now[i]-=ned[i];
        continue;
    }
    ned[i]-=now[i],now[i]=0;
    tmp[a[i]]+=ned[i],tmp[b[i]]+=ned[i];
}

接着，只需要判断是否有金属还是缺少即可。如果没有缺少金属，说明该答案是合法的。

bool flg=1;
for(int i=1;i<=n;i++){
    if(tmp[i]>INF) return 0;
    if(tmp[i]) flg=0;
    ned[i]=tmp[i],tmp[i]=0;
}
if(flg) return 1;

另外，对于非递归版检查函数，金属需求的下传显然执行最多 n 次。整理一下，检查函数如下：

vector<ll>ned(n+1),tmp(n+1),d=c;
ned[1]=mid;
for(int _=1;_<=n;_++){
    for(int i=1;i<=n;i++){
        if(ned[i]<=d[i]){
            d[i]-=ned[i];
            continue;
        }
        ned[i]-=d[i],d[i]=0;
        tmp[a[i]]+=ned[i],tmp[b[i]]+=ned[i];
    }

    bool flg=1;
    for(int i=1;i<=n;i++){
        if(tmp[i]>INF) return 0;
        if(tmp[i]) flg=0;
        ned[i]=tmp[i],tmp[i]=0;
    }
    if(flg) return 1;
}
return 0;

AC code

#include<bits/stdc++.h>
using namespace std;
#define all(vec) vec.begin(),vec.end()
#define fr first
#define sc second
#define pq priority_queue
#define gr greater<int>
using ll=long long;
using db=double;
using i128=__int128;
using pii=pair<int,int>;

const ll INF=1e12;

void solve(){
    int n;
    cin>>n;
    vector<int>a(n+1),b(n+1);
    vector<ll>c(n+1);
    for(int i=1;i<=n;i++) cin>>a[i]>>b[i];
    for(int i=1;i<=n;i++) cin>>c[i];

    auto check=[&](ll mid){
        vector<ll>ned(n+1),tmp(n+1),d=c;
        ned[1]=mid;
        for(int _=1;_<=n;_++){
            for(int i=1;i<=n;i++){
                if(ned[i]<=d[i]){
                    d[i]-=ned[i];
                    continue;
                }
                ned[i]-=d[i],d[i]=0;
                tmp[a[i]]+=ned[i],tmp[b[i]]+=ned[i];
            }

            bool flg=1;
            for(int i=1;i<=n;i++){
                if(tmp[i]>INF) return 0;
                if(tmp[i]) flg=0;
                ned[i]=tmp[i],tmp[i]=0;
            }
            if(flg) return 1;
        }
        return 0;
    };

    ll l=0,r=1e12;
    while(l<r){
        ll mid=(l+r+1)>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }

    cout<<l<<'\n';
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int T=1;
    cin>>T;
    for(int i=1;i<=T;i++){
        cout<<"Case #"<<i<<": ";
        solve();
    }
    return 0;
}