P10544 [THUPC2024] 转化

Hanghang · 2024-06-20 10:44:51 · 题解

P10544 [THUPC2024] 转化

来个暴力做法。

对每个物品的答案分别处理。设当前处理的物品为 z。

设 f_{t,i} 表示经过了至多 t 次转换，用一个 i 最多能转化出 f_{t,i} 个 z 物品。

那么最终的答案为 \sum f_{+\infty,i}\times a_i，a_i 为初始 i 的物品个数，转移即枚举每种转移条件更新即可。

注意到这种松弛至多 n 次，如果还能继续松弛那么说明物品可以无穷多。

复杂度为 O(n^3m)，实测非常快。

#include<bits/stdc++.h>
using namespace std;

typedef __int128 ll;
const int N=103,M=1003;
ll n,m,sum,a[N],f[N],g[N],c[M],len[M],b[M][N];
void write(ll X)
{
    if(X<0){putchar('-');X=~(X-1);}
    int s[50],o=0;
    while(X){s[++o]=X%10;X/=10;}
    if(!o)s[++o]=0;while(o)putchar(s[o--]+'0');
    putchar('\n');
}
int main()
{
    int _n,_m;cin>>_n>>_m;n=_n;m=_m;
    for(int i=1,x;i<=n;i++)cin>>x,a[i]=x,sum+=n*a[i];
    for(int i=1;i<=m;i++)
    {
        int _c,_len;cin>>_c>>_len;c[i]=_c;len[i]=_len;
        for(int j=1,x;j<=len[i];j++)cin>>x,b[i][j]=x;
    }
    for(int t=1;t<=n;t++)
    {
        ll fl=0;
        for(int i=1;i<=n;i++)f[i]=i==t;
        for(int tim=1;tim<=n;tim++)
        {
            for(int i=1;i<=n;i++)g[i]=f[i];
            for(int i=1;i<=m;i++)
            {
                ll x=0;
                for(int j=1;j<=len[i];j++)x+=g[b[i][j]];
                f[c[i]]=max(f[c[i]],x);
            }
            ll cnt=0;
            for(int i=1;i<=n;i++)cnt+=f[i]==g[i];
            if(cnt==n)break;
            fl|=tim==n;ll s=0;
            for(int i=1;i<=n;i++)s+=f[i]*a[i];
            if(s>(ll)1e33){fl=1;break;}
        }
        ll s=0;
        for(int i=1;i<=n;i++)s+=f[i]*a[i];
        if(fl)cout<<"infinity"<<endl;
        else write(s);
    }
}