自动搬运

查看原文

来自洛谷，原作者为

	Doubleen 你好！

搬运于2025-08-24 22:11:10，当前版本为作者最后更新于2018-08-27 11:32:02，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先，这是一道图论题，$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，讲的太差请见谅