首页 > 代码库 > CF:Problem 427C - Checkposts强连通Tarjan算法

CF:Problem 427C - Checkposts强连通Tarjan算法

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

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

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

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

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

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#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<int>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<q[u].size(); j++)
    {
        v=q[u][j];
        if(!DFN[v])
        {
            tarjan(v);
            LOW[u]=min(LOW[u],LOW[v]);
        }
        else if(vis[v]&&DFN[v]<LOW[u])
            LOW[u]=DFN[v];
    }
    if(DFN[u]==LOW[u])
    {
        Count++;
        int x=0,y=INF;
        do
        {
            v=q2[tem--];
            vis[v]=0;
            suo[v]=Count;
            if(y>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<<sum<<‘ ‘<<tmp<<endl;
}
int main()
{
    cin>>n;
    int u,v;
    for(int i=1;i<=n;i++) sca(bb[i]);
    sca(m);
    for(int i=0;i<m;i++)
    {
        sc(u,v);
        q[u].push_back(v);
    }
    solve();
    return 0;
}