CF:Problem 427C - Checkposts强连通Tarjan算法 - c++编程基础

这题昨晚做了，刚开始看题的时候没想出好法子，然后就看D题了，一看D题发现是后缀数组，然后就把模板改了点就交了上去……不幸的是……WA了，然后重新看题，果然题目看漏了……不仅要用后缀数组和前缀数组求出公共子缀，还要是求最小的，而且在每个串里都不能重复的，这下就想了会不会了，然后看见大帝C过了，然后就重新回来看C了，看了会终于明天怎么做了。

C题意：给个图，然后每个点都有权值，求最小的花费及方案数；最小的花费是这样的：因为是建立一个岗哨，然后这个岗哨可以管哪些呢，可以管 i = j 的，或者可以从 i 出发到 j ，然后还可以从 j 出发回到 i 的，注意题目给出的是单身图，所以从 i 出发到 j ，不一定能从 j 回到 i 。

思路：根据题目要求可知：最小花费就是求出一些点，然后这些点的权值之和最小，并且这些点都能管住所有的点（即所有的点都能被自身或者被其他的点管着，不能漏了）。又因为要求出方案数，为什么有方案数这一说呢？因为如果两个点的权值相同，然后又互相连通，那么这就有两种方案了是吧！所以说到这里就可以知道用强连通做了！

每个强连通里取最小的值之和就是最小花费了，然后每个强连通里最小值的个数相乘当然就是方案数啦！！！因为每个最小树值的结点都可以建立岗哨嘛，然后都是连通的当然建立一个就行咯，方案数就是这样滴咯！

昨晚敲了一个小时，唉……在强连通里求方案的时候一直出错，只过了3个样列，然后一直改到比赛结束了还没得交！可惜了！刚才重新做直接就在Tarjan求强连通那do-while里面就可以直接求出最小花费和方案数了，昨天是在main函数里面做一直出错不知道为啥不行，其做法实质都是一样的啊，唉……写挫了昨晚

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         #include 
        
          #include 
         
           #include 
          
            #include 
           
             #include 
             #include 
             
               #include 
              
                #define PI acos(-1.0) #define mem(a,b) memset(a,b,sizeof(a)) #define sca(a) scanf("%d",&a) #define sc(a,b) scanf("%d%d",&a,&b) #define pri(a) printf("%d\n",a) #define lson i<<1,l,mid #define rson i<<1|1,mid+1,r #define MM 400005 #define MN 100005 #define INF 1000000007 #define eps 1e-7 using namespace std; typedef long long ll; int n,m,cnt,tem,Count,DFN[MN],LOW[MN],vis[MN],suo[MN],q2[MN]; vector
               
                q[MN]; int bb[MN]; ll sum,tmp=1; void tarjan(int u) { int j,v; DFN[u]=LOW[u]=++cnt; vis[u]=1; q2[++tem]=u; for(j=0; j
                
                 bb[v]) x=1,y=bb[v]; else if(y==bb[v]) x++; } while(v!=u); sum+=y,tmp=tmp*x%INF; } } void solve() { int v,i,j,kk=0; Count=cnt=tem=0; mem(DFN,0); for(i=1; i<=n; i++) if(!DFN[i]) tarjan(i); cout<
                 
                  >n; int u,v; for(int i=1;i<=n;i++) sca(bb[i]); sca(m); for(int i=0;i