题解 P2811 Protect the school

· · 题解

前置知识

tarjan

缩点

题意

有 n个点，m条边，每个点有一个点权，求选择某些点后，使得每个点始终能够到达，且选择的点权和最小，并求出点权和最小的方案数。

分析

为什么要缩点？

题目中要求最少的保安，而一个保安就可以控制一个环，所以可以用缩点求出最少的保安数。

如何理解始终？

就是说，你在处理一个紧急事件后，仍旧能够处理其他所有的紧急事件，讨论区中有一个比较有趣的问题，是对样例的错误分析，我们把样例搞出来。

疑问是：选择 3、4后图就是能够到达的，但是出现了一个问题：3处理了 5之后，这个保安便不能再回到 3了，所以说没有满足始终这个约束条件。

所以我们得出，缩点后，每个点的值（或者环中的最小值）的总和便是我们要求的最小点权和，至于方案数，每个环中可能有多个最小值，使用乘法原理解决即可。

代码部分

#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
vector <int>a[10010];
int sta[10010],top=0,flag[10010],num,tot,col[10010],ss[10010];
int ans,va[10010],dfn[10010],low[10010],ans1=1,mm[10010],nn[10010],sc[10010];
void tarjan(int x)//标准tarjan缩点
{
    sta[++top]=x;
    flag[x]=1;
    dfn[x]=low[x]=++num;
    for(int i=0;i<a[x].size();i++)
    {
        int y=a[x][i];
        if(!dfn[y])
        {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        }
        else
        {
            if(flag[y])
            {
                low[x]=min(low[x],dfn[y]);
            }
        }
    }
    if(dfn[x]==low[x])
    {
        tot++;
        while(sta[top+1]!=x)
        {
            col[sta[top]]=tot;
            ss[tot]+=va[sta[top]];
            flag[sta[top--]]=0;
        }
    }
}
int read()
{
    char c=getchar();
    int x=0;
    while(c<'0'||c>'9') c=getchar();
    while(c>='0'&&c<='9')
    {
        x=x*10+c-'0';
        c=getchar();
    }
    return x;
}
int main()
{
    memset(mm,0x3f,sizeof(mm));
    int n,m,u,v;
    n=read();
    for(int i=1;i<=n;i++)
    {
        va[i]=read();
    }
    m=read();
    for(int i=1;i<=m;i++)
    {
        u=read(),v=read();
        a[u].push_back(v);
    }
    for(int i=1;i<=n;i++)
    {
        if(!dfn[i]) tarjan(i);
    }
    for(int i=1;i<=n;i++)//把点或者环的最小值处理出来，并且统计最小值的数量
    {
        if(!sc[col[i]])
        {
            sc[col[i]]=col[i];
        }
        if(va[i]<mm[col[i]])
        {
            mm[col[i]]=va[i];
            nn[col[i]]=1;
        }
        else
        {
            if(va[i]==mm[col[i]])
            {
                nn[col[i]]++;
            }
        }
    }
    for(int i=1;i<=n;i++)//一加一乘，解决战斗
    {
        if(sc[i])
        {
            ans+=mm[sc[i]];
            ans1*=nn[sc[i]];
        }
    }
    cout<<ans<<" "<<ans1<<endl;
}

蒟蒻实力不足，有问题欢迎指出