程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> CF:Problem 427C - Checkposts強連通Tarjan算法

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];
vectorq[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; jbb[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