zoj3795 Grouping --- 良好的沟通，寻找最长的公路-白红宇

zoj3795 Grouping --- 良好的沟通，寻找最长的公路

阅读量：4974 次

发布时间：2019-06-12

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

给定一个图，为了保持图分裂至少成多个集合的集合内可以使点没有直接或间接的关系。

首先，题意可以得到图中可能含有环。该环的内侧是肯定是要被拆卸。

图点降低建DAG画画，能想象。。图从零点渗透深入，在点中的一组相同的水平是不相关，

那么题目所求的问题就转化成求图中最长路的问题了。

这个题的实质和事实上是一模一样的。

。

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             #define inf 0x3f3f3f3f#define eps 1e-6#define ll __int64#define M 100010//图中点数using namespace std;int sta[M],top; //Tarjan 算法中的栈bool vis[M]; //检查是否在栈中int dfn[M]; //深度优先搜索訪问次序int low[M]; //能追溯到的最早的次序int ccnt; //有向图强连通分量个数int id; //索引號vector
              
                e[M]; //邻接表表示vector
               
                 part[M]; //获得强连通分量结果int inpart[M]; //记录每一个点在第几号强连通分量里int degree[M]; //记录每一个强连通分量的度vector
                
                  edge[M];//缩点后建图int ans,n,m,dp[M],in[M],point[M];void tarjan(int x){ int i,j; dfn[x]=low[x]=id++; vis[x]=1; sta[++top]=x; for(i=0;i