刷题？作业狂魔！

· · 题解

首先，这是一道图论题，n=10000就是暴力dfs求解。但是有一个环的限制，因此先用tarjan把环的作业去除，再dfs就可以了

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const ll M=10005;
ll v[M],c[M],t[M];
struct node{
    ll to,next;
}edge[M*11];
ll head[M],cnt;
bool vis[M],can[M];
ll dfn[M],low[M],sta[M],in[M],color[M];
ll top,sum,tot,ans;
inline void add(ll x,ll y){edge[++cnt]=(node){y,head[x]},head[x]=cnt;}
inline ll read()
{
    ll x=0,f=1; char ch=0;
    while(!isdigit(ch)) f=(ch=='-'?-1:1),ch=getchar();
    while(isdigit(ch)) x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*f;
}
void tarjan(ll x)
{
    dfn[x]=low[x]=++tot;
    sta[++top]=x; vis[x]=true;
    for(register ll i=head[x];i;i=edge[i].next)
    {
        ll u=edge[i].to;
        if(!dfn[u]){
            tarjan(u);
            low[x]=min(low[x],low[u]);
        }
        else if(vis[u]){
            low[x]=min(low[x],dfn[u]);
        }
    }
    if(dfn[x]==low[x]){
        ll jsq=1;
        color[x]=++sum; vis[x]=false;
        while(sta[top]!=x){
            jsq++;
            color[sta[top]]=sum;
            vis[sta[top--]]=false;
        }
        if(jsq>1) can[sum]=true;
        top--;
    }
}
void dfs(ll x,ll s,ll la)
{
    ans=max(ans,s);
    for(register ll i=head[x];i;i=edge[i].next)
    {
        ll u=edge[i].to;
        if(can[color[u]]) continue;
        if(la>=c[u]*t[u]) dfs(u,s+c[u]*v[u],la-c[u]*t[u]);
        else ans=max(ans,s+(la/t[u])*v[u]);
    }
}
int main()
{
    ll n=read(),T=read();
    for(register ll i=1;i<=n;i++){
        v[i]=read(); c[i]=read(); t[i]=read();
    }
    ll m=read();
    for(register ll i=1;i<=m;i++){
        ll x=read(),y=read();
        add(x,y); in[y]++;
    }
    for(register ll i=1;i<=n;i++){
        if(!dfn[i]) tarjan(i);
    }
    for(register ll i=1;i<=n;i++){
        if(in[i]||can[color[i]]) continue;
        if(T>=c[i]*t[i]) dfs(i,c[i]*v[i],T-c[i]*t[i]);
        else ans=max(ans,(T/t[i])*v[i]);
    }
    printf("%lld\n",ans);
    return 0;
}

那个别忘了吸氧哦QAQ，讲的太差请见谅