bzoj5450 轰炸-白红宇

bzoj5450 轰炸

阅读量：6817 次

发布时间：2019-06-26

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

分析

不难想到如果这个图是一个DAG则答案就是图的最长路

于是我们考虑有环的情况

我们发现一个环上的所有点颜色一定不相同

于是我们发现答案就是缩点之后跑一遍点权最长路

点权就是这个强联通分量中的点的数量

注意求最长路的时候要用拓扑排序求

代码

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             #include
             
              #include
              
               #include
               
                #include
                
                 #include
                 #include
                  
                   using namespace std;vector
                   
                    v[1001000],nv[1001000];int n,m,dfn[1001000],low[1001000],ist[1001000],sum,cnt;int belong[1001000],d[1001000],w[1001000],du[1001000],vis[1001000];stack
                    
                     a;queue
                     
                      q;inline void tarjan(int x){ dfn[x]=low[x]=++cnt; a.push(x); ist[x]=1; for(int i=0;i