ZROI2018提高day1t2-白红宇

ZROI2018提高day1t2

阅读量：5842 次

发布时间：2019-06-18

本文共 1421 字，大约阅读时间需要 4 分钟。

分析

考场上看错了第一个条件，于是觉得是个简单贪心，随便取了每一个点的最大收益然后算了一下，就得了40pts...看来读对题很重要呀qwq。实际的正解是这样的：我们将每一个i与f[i]连一条边，这样就构造出了一个基环内向树。我们记录到达每一个点的最大收益与次大收益，而对于每一个点我们均可以先取a[i]-1次最大收益。之后我们通过画图可以发现，对于一个环内，肯定会有一个节点取不到环边价值。所以我们枚举环上所有点（这个可以用tarjan解决），如果存在一个点i满足到达这个点的环边不是最大收益则这个环对于答案没有任何改变，否则找到一个点i使得这个点是环上最大收益-次大收益最小的点，然后在最终答案减掉这个值就可以了。

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;const long long inf = 1e15+7;vector
                   
                    v[100100];long long wh[100100],A[100100],maxn[100100],secn[100100];long long f[100100],c[100100],d[100100];long long dfn[100100],low[100100],ist[100100],ans,cnt;stack
                    
                     a;inline void tarjan(long long x){ dfn[x]=low[x]=++cnt; a.push(x); ist[x]=1; for(long long i=0;i
                     
                      1)ans-=minn; } return;}int main(){ long long n,m,i,j,k; memset(maxn,0,sizeof(maxn)); memset(secn,0,sizeof(secn)); scanf("%lld",&n); for(i=1;i<=n;i++)scanf("%lld%lld%lld%lld",&f[i],&c[i],&d[i],&A[i]); for(i=1;i<=n;i++){ v[i].push_back(f[i]); if(d[f[i]]-c[i]>maxn[f[i]]){ secn[f[i]]=maxn[f[i]]; maxn[f[i]]=d[f[i]]-c[i]; wh[f[i]]=i; }else secn[f[i]]=max(secn[f[i]],d[f[i]]-c[i]); } for(i=1;i<=n;i++) ans+=maxn[i]*A[i]; for(i=1;i<=n;i++) if(!dfn[i])tarjan(i); printf("%lld\n",ans); return 0;}

转载于:https://www.cnblogs.com/yzxverygood/p/9557625.html

你可能感兴趣的文章